rng_58's blog

AtCoder Grand Contest 029
By rng_58, history, 6 years ago, In English

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.

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

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

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

E
F
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -57 Vote: I do not like it

    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.

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

      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).

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

        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.

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

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

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

        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?

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

          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.

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

            What strategy? That the first guy should always go down? Yes, that's very hard.

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

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

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

            That we need to count the number of inversions.

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

              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.

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

                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.

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

                  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.

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

                  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.

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

                  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).

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

                  Yes we can ;)

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

      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!

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

        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.

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

          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).

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

            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.

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

              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".

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

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.

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

    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.

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

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

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

    We need to move to GP450 ASAP!

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

Thanks for the contest!

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

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

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.

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

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

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

The English editorial is ready now.

→ Reply