rng_58's blog

AtCoder Grand Contest 013
By rng_58, history, 8 years ago, In English

AtCoder Grand Contest 013 will be held on Saturday (time). The writer is maroonrk.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1600 — 2000. Note that the contest duration is unusual (150 minutes).

Let's discuss problems after the contest.

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

Comments Comments (20)
| Write comment?
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

The video editorials you upload on AtCoder live can you please at least provide english subtitles for the international community participating in your contests, as we could also experience your thought process in coming up with the solutions. This would be of much help. Thanks.

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

    Adding subtitles is a lot of work. They already provide well-prepared editorials, I wouldn't ask for more.

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

      Don't ask then. You can learn Japanese instead.

      I'm not so ambitious and would be very glad for english subtitles or the whole video.

      If you add some feature to the international website it's good to do it in English at some point (if not at the beginning).

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

        I think this is called "courtesy abuse" (/nadużywanie uprzejmości). If someone is doing something good for me for free I think I am in no position to demand more. Of course this depends on a specific situation, for example if I think there could be some feature on codeforces that would be helpful to many people then I can politely request, but this would require just a single effort whereas adding subtitles is a permanent addition of a lot of work when I think they are unnecessary since detailed English editorials are always posted.

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

          How do you know they do this for free? I do not know their business model, but I assume that the more users, the more profit. And the more international features to delight customers, the more users.

          Besides I did not see anything impolite in the initial ask. They can say either yes or no — it was just a nice suggestion.

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

            Yeah, I don't say it was impolite, it was rather really polite, but I just thought it would be too much to request ;p.

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

          nadużywanie uprzejmości

          Holy shit...

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

            Huh, I see you are from Tallinn and just said "Holy shit" : D. That brings back terrible memories that haunt me up to this day. About literally by far the worst shot I have ever drunk. It was in Tallinn in Valli Bar and that shot was called "Holy Shit". We were enchanted by its deceiving looks. It was brownish and was decorated with whipped cream! We thought that it would be very sweet and pleasant to drink. I was never so wrong in my life. Words cannot express how terrible it was. I felt burning in my throat even after hour after this. n-1 of us were suffering in agony. But I-won't-say-who said: "But guys, it was good!"

            Sorry for offtop, but I just had to share it xD. Remember, keywords: Valli Bar, Holy Shit. Do this, I recommend :D But once in life, not more :P.

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

              I wonder how do you manage to code, if you can be killed with one shot?

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

                Everybody can be killed with one shot (e.g. from pistol)

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

Alert: Starts in 10-mins.

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

Problem C today is problem F from Educational Round 10 on Codeforces.

Also, that's escalated quickly (in term of difficulty).

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

Can someone please explain how to avoid double counting using "special operations" in D as mentioned in the editorial? Also, how can we perform RR or RB when x=0 (i.e. no red ball is present)?

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

Reading C's editorial after spending 2 hours on it like

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

    And now I am still confused about C. Can you give me some clearer explanation on it? Thank in advance.

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

Why does my solution TLE for 'A'? It runs in O(n) i think. http://agc013.contest.atcoder.jp/submissions/1221485

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

    warning: control reaches end of non-void function

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

How to solve B ???*UPD* Editorial updated .Ignore

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

It's possible to solve problem D in O(max(n, m)). First, we observe, that we need to count number of sequences (x1, ..., x2m) such that x1 =  ± 1, xi = xi - 1 ± 1 and there exists z such that z is even and . So, we need to count number of paths that have small difference between maximal and minimal value. This can be done using inclusion–exclusion principle.

Now we need to solve the following problem: for fixed a ≥ 0, b ≤ 0, a and b is even, find the number of paths of length 2m, which don't cross lines y = a and y = b. There is a simple formula for this value, but I don't remember the proof. You can check my code here. First I fix diff = (a - b) / 2. Then I calculate val — the number of paths in case a = diff, b = 0. Then at each step I subtract 2 from b and from a and calculate new number of paths.

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

    Can you, please, explain your idea a little better? I don't get it why what we're asked to compute is equivalent to counting those sequences. I don't see how you considered inserting new bricks at each step in your solution. Generally, I'd be more interested in how are the 2 problems equivalent and exactly what bijection we have between a sequence x1, x2, ..., x(2m) and a path that you described.

    → Reply