Блог пользователя rng_58

Автор rng_58, история, 6 лет назад, По-английски

AtCoder Grand Contest 029 will be held on Saturday (time). The writer is yutaka1999. This contest counts for GP30 scores.

Contest Link

Contest Announcement

Contest duration: TBD (around 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

  • Проголосовать: нравится
  • +111
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry for the delay of editorial translation. Meanwhile, some hints for E/F:

E
F
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -57 Проголосовать: не нравится

    This round had really bad scoring. D was easier than A, but for some reason costs more than C or D. And F was not harder than E but costs almost two times more.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's hard to estimate the difficulty and we thought F is very hard. But judging from the number of ACs, I think the order of problems was correct (may be C/D can have the same score).

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +37 Проголосовать: не нравится

        There is always a bias in number of accepted solutions towards earlier problems, because some retards like me don't read the next problem until they solved the current one.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      "D was easier than A" — how do you want to be treated seriously when you're saying things like this?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится -16 Проголосовать: не нравится

        A required at least some ideas, while D is just simulating the process until we bump into an obstacle. What's so hard about that?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          I think you don't remember what A asked for. D required a simulation provided you found out the strategies. I also found it easier than B and C, but that's because my solution to B is overovercomplicated and for some reason I simply couldn't think about C. However, saying shit like D was easier than A is the definition of an exaggeration.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ok, so saying in your language, what idea in A are you talking about?

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            That we need to count the number of inversions.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +13 Проголосовать: не нравится
              1. I've just calculated for each B the number of W-s it will be swapped with. I didn't realize that this is the same as calculating inversions, however it's obvious, of course.

              2. Calculating the number of inversions in a binary word is, again, much easier than calculating the number of inversions in general.

              3. Do you really find this observation with inversions harder than coming up with the solution for D? I mean, as for me, one can come up with a solution for A more instantly after reading the statement than for D. And it's without implementing.

              TL;DR: yes, that [number of inversions equivalence] is very hard.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится

                Yes, of course I didn't write general algorithm for inversions, I did it the same way as you. And I didn't say that it's hard. But I can understand that for someone it may not be obvious. What I can't understand is how someone can try to solve D and fail. I have no idea how this can happen. Like what way of thinking you must choose to not come up with a solution? Seeing people like qwerty787788 and Swistakk not solving it blows my mind. It's like seeing red coder failing to solve A+B. I don't want to insult them, and don't think that they are stupid, in fact they are much smarter than me. But I'm honestly very confused right now.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  I pretty much solved it, but forgot "-1" in one place and abandoned this problem xD. AC in upsolving short time after end of contest.

                  Maybe that's not something mind blowing, but maybe I will regain 10% of respect I lost by taking this 447th place xD.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  D was harder than A because of the implementation and because of the ("extremely tough") observation that if the first guy will stop then the games ends. Also because it was scored with 800 it was confusing how could a solution so obvious be right.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Yes, I agree that it was harder to implement than A, I didn't take this into consideration. But your argument about scoring is exactly the reason of my complaint: that it should not have score of 800 and it definitely should not have more points than B and C(I hope we can agree at least on that).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Yes we can ;)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      To join the downvote party, I also think A was harder than D, and don't know why D was proposed at all.

      I could solve A fast, as the inversion invariant idea was well known. However, D was simply translating the problem statement into code, with the idea being... umm.. that Takahashi can't stop?

      Even B and C was not that easy for me, so it was pretty clear that something is wrong with my understanding. but I really couldn't found my misinterpretation, so I wrote down the code in worry and got an uncanny AC.

      Btw, I enjoyed all other problems very much. Thanks for problemsetter!

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        I agree that D is a little bit silly once you see what the problem is talking about, but clearly not everyone was thinking in the same way as you, or there would be more solves...

        (For example, if you consider dp[x][y] of how many more moves starting from position x, y, then you won't really get to this solution...)

        However, problem A is probably one of the most (if not the most) textbook and straightforward problems to ever appear on an AGC, I don't see how its difficulty can be compared with any other problem with any content at all.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          To be frank, A took me something like 1 minute to came up with solution (what I mean is that 1 minute is rather long, not rather short :D), so I can explain you why it was not obvious to me. Statement was talking about some token with two colored sides and operation described was flipping colors of two neighbouring tokens. In this way it was completely not clear to me how to solve this problem and if it wasn't for its point value I would think it is at least a bit challenging problem cause I didn't see any good way of grasping that concept of changing colors. However then I observed that instead of thinking of two tokens staying in their place but changing their colors I observed that it can be thought of as two tokens with different colors keeping their colors but swapping their positions. Once stated, it is completely obvious that these two interpretations are equivalent, just a bit different way of putting the same thing in words, however in this second way it was completely obvious for me how to solve it. See the difference and why that matters so much?

          Tbh on second thought I think that my thinking process was a bit different. Being clueless, I decided to investigate samples and see some patterns and I just noted that answer is what it is (sum of number of Bs on left over Ws) and realized why it is like that by following that process I described in previous paragraph (which after noting this pattern was so obvious it took me sth like 1 second after being clueless for cosniderably longer time).

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Sure, if you go by that measure of difficulty...

            Can you really imagine someone in division 1 getting stuck on A though? On the other hand, it's very easy to imagine someone not knowing how to solve D after some time.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              My main goal was to illustrate how different way of thinking about basically the same thing may lead to someone coming up or not with a solution, because sometimes someone's problem lies in a different place than we think.

              And I surely think that A is easier than D and my first thought to D was designing that dp table as you described (then I noted N<=2e5 and abandoned this idea and quickly came up with right approach). But as I was clueless about A for 1 minute, I can imagine some other participant being stuck on this for much longer because of lacking step "first way of thinking -> second way of thinking", but I can't imagine div1 guy being stuck on step "second way of thinking -> proper solution".

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is the following greedy for problem C correct?

Given that c distinct characters were used in the first i - 1 strings, to find the string Si: find the lexicographically smallest string X composed by at most c distinct characters which is greater than Si - 1. If it exists, make Si = X. Otherwise, find the lexicographically smallest string Y composed by at most c + 1 distinct characters which is greater than Si - 1, make Si = Y and make c = c + 1.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    I implemented this initially but i think it's incorrect, consider a case where there are only 2s in input and you run your greedy which generates sequence, "aa", "ab", "ba", "bb", "bc" .. if you observe you missed "ac" because at the time of generating 3rd string, character c was not allowed. So this approach will fail on below test case:

    9
    2 2 2 2 2 2 2 2 2
    

    So, i approached this with doing binary search on number of characters allowed and check if that is fine.

»
6 лет назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

How many GP30 points do I get for taking 447th place?

»
6 лет назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

Thanks for the contest!

My screencast with commentary: https://youtu.be/02VV330Avc8

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

It might be irrelevant, but I'd like to mention that editorial of AGC028 is still uncompleted (for problem F).

UPD: Now it is completed.

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

So...where can I see the editorial? It's not present in the Atcoder contest front page.

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

The English editorial is ready now.