When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Errichto's blog

By Errichto, 4 years ago, In English

Hi. I invite you to AtCoder Grand Contest 047.

Statements are very short and I think that problems are interesting. Big thanks to rng_58 for discussing problems with me.

I will likely make a short live stream just after the contest ends. (update: watch the recording here)

UPD, congrats to tourist for winning and Benq for the second full score.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Grand contests have a rated range of 1200~inf i guess.

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

Wow, a non-Japanese writing an AGC? I thought the writers had to be exclusively from within AtCoder. Anyhow, should we expect a usual AGC or are the problems less AtCodery than usual?

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

    You are right. I and tourist had to change our nationality to Japanese.

    Anyhow, should we expect a usual AGC or are the problems less AtCodery than usual?

    It was still rng_58 who accepted and rejected problems :)

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

      After a couple of months my AGC was already forgotten!

      In any case, I'd like to give some feedback on your contest, because I feel that what is written in this thread is a bit too harsh. I will not talk about F since I have not read the statement.

      A: Ok easy problem. It's not a deep idea but it required at least a minute of thinking and then implementing it was not painful at all (I read the numbers as strings).

      B: This was very bad for me because it required $$$0$$$ thinking and not $$$0$$$ implementation time. It is just a boring variation over the more classic "Count pairs of strings (S_i, S_j) such that one is a prefix of the other".

      C: Differently from all the other reds in this thread, for me this was very good. I did not know the idea of using the generator and I spent a huge amount of time before having it. I had fun solving it and it was cool having the "Aha!" moment. Implementation was, without any doubt, easy (of course, I copy-pasted FFT).

      D: I solved this one in contest, but did not manage to implement it. Ok problem.

      E: During the contest I could not solve it (not even the easy subtask) after thinking about it for ~15 minutes. After contest I solved it and I like the solution. Even though it's not the kind of problems I like, it was a nice one.

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

        Damn it, I feel stupid for forgetting the Italian round after spending so many hours to solve it (and not without hints).

        I'm happy that the experience with C was as intended at least for some people :D

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

Wow. Errichto is back at making contest.

»
4 years ago, # |
Rev. 3   Vote: I like it -126 Vote: I do not like it

[DELETED]

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

deleted

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

    There is a 23-hour difference in their start time.

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

why the duration shrinks?

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

    If you're talking about initial value of 110 minutes on the contest page, that's default value and should be replaced with ???, I guess.

    Anyway, everything's decided now, the duration is 2h20m.

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

The contest starts in less than 1 hour.

See you on https://www.twitch.tv/errichto just after the contest, I will answer questions and talk a little bit about contest preparation.

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

    Can you reschedule doubts session after CF Round 663 DIv2 for DIv2 participants.

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

      I don't think a guy who participate in div.2 should participate in AGC too. (rng_58 said that AGC are for the high reds

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

        Actually I often participate for Getting something new as AGCs are too awesome if we see their problems getting a blend of concepts. May be I am wrong! As I don't know much about what other mindsets.

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

Hoping to have a GREAT contest!

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

good luck all))

»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Solved A and B but the round is not rated for me. My luck always.

»
4 years ago, # |
  Vote: I like it -135 Vote: I do not like it

For problem A, I'm getting WA on test case 5 and TLE after test case 5

here is my code

any help would be appreciated!

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

    First: asking anyone for help during contest is cheating. Second: You get TLE because your code in $$$O(n^2)$$$ with $$$n \leq 200\,000$$$ And you can get WA on test like:

    2
    9999.000000001
    9998.999999999
    

    Correct answer is $$$0$$$, while your code outputs $$$1$$$. What happened is: the input is $$$9999 + 10^{-9}$$$, $$$9999 - 10^{-9}$$$ so their product equals $$$9999^2 - \left(10^{-9}\right)^2 = 99980001 - 10^{-18}$$$, which is not an integer, but is so close to an integer, that if you compute it using double/long double it will be rounded to 99980001 which is an integer.

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

is this contest have pair?

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

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

    As long as topics and solutions are completely different, I don't see anything wrong there.

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

      Nothing wrong with it, I just thought it was funny. :P

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

Good problem set. How to solve C?

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Nice contest Errichto!, anyway problem C can be solved in O(nsqrt(p))?

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

I think Problem C is quite standard.

The idea behind problem E is really interesting. How to solve it?

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

It seems nowadays codeforces has better problems than atcoder...

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

    Can you elaborate? What's there other than C being known?

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

      Maybe that's just me, I can't say anything about DF, but I find AB uninteresting :(

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

      A: boring.

      B: write trie(or hashes)

      C: write FFT

      E: easy part requires no ideas at all, hard part requires one idea: check all pairs of bits. Other than that you just need to write annoying function that checks if the $$$i$$$-th bit is 0 or 1.

      D: unordered_map gets TL. Usually I'd say it's my fault, but after other 4 problems about implementation having one about constant optimizations was too much for me.

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

        Thanks for the feedback! AB aren't really interesting, I agree. I see some other issues but I disagree with those you described.

        B: write trie(or hashes)

        The problem is: understand the described process, figure out that's TRIE after reversing strings, put things in TRIE, do something extra in a created tree (either dp or going up through paths). I would say that implementing TRIE is the smallest/easier out of these 3-4 steps. Is trie even harder than segment trees? It's 10 simple short lines, takes 2 minutes. It's only one-fourth of my whole code. (While it's bad and I would prefer B with shorter solution, I'm arguing that TRIE here was just a simple tool to use.)

        code

        C: write FFT

        If an AGC participant wants to solve C-F problems, they most likely just copy-paste FFT. Doing convolution was supposed to be the easiest part of this problem. Again, steps are: figure out that it's convolution after reordering with primivite root, find primitive root, do convolution, avoid double counting. Copy-pasting FFT takes 1 minute. Thoguh, I'm sad and surprised that it was obvious for people that we should use primitive root in this problem.

        E: easy part requires no ideas at all, hard part requires one idea: check all pairs of bits. Other than that you just need to write annoying function that checks if the i-th bit is 0 or 1.

        The idea of what to do is easy. It's difficult how to do it. If it's easy and codes are relatively short, how do people spend 1 hour on average in this problem? It shouldn't be about off-by-one errors or corner cases. I would say that once you figure out the next tool/blackbox/trick, it's very easy to implement it and run on on sample input values to check if it works. I would say that this problem can be solve by spending one hour with pen and paper, then 10 minutes with computer. And that makes a nice problem.

        D: unordered_map gets TL. Usually I'd say it's my fault, but after other 4 problems about implementation having one about constant optimizations was too much for me.

        I partially agree that it's bad and so does rng_58. He hates situations with too-slow-solutions being slightly too slow and I agree with him. We heavily discussed TL and ML in this problem and he even considered removing the problem just because of this. In your solution, using a map with $$$O(L \cdot H^3)$$$ time complexity is hopeless and using unordered_map isn't significantly faster. I think that your solution is at least 5 times too slow and it needs more than 1GB of memory. It was just not a good approach.

        so basically, I expected CDEF to be very nice problems and for sure I misjudged C (the part about coming up using primivite root)

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

          Just a small note about problem D:

          I think that your solution is at least 5 times too slow and it needs more than 1GB of memory. It was just not a good approach.

          While in general I agree with your last statement, I just want to point out that it was still possible to squeeze in this specific approach: submission.

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

          Is trie even harder than segment trees? It's 10 simple short lines, takes 2 minutes. It's only one-fourth of my whole code.

          Yes, trie is quite easy to implement, but I didn't know this thing and was surprised... (Because trie problems contains other painful elements usually?)

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

          For me the situation was thinking time <<< coding time for all of ABCDE, it seems the same for aid and maybe some other people, and I surely understand that is not your case. So it might be hard for us to agree on the impression on the problems (especially on D, for which I did a not-so-long but longer-than-you implementation without much thinking).

          (E:) I would say that this problem can be solve by spending one hour with pen and paper, then 10 minutes with computer.

          This is for the writer, a very accurate coder, or a very lucky person. One can easily mistake the variable slot (even without hardcoding the indices), one can easily mistake the order of i j k, one can very easily forget to output the number of lines. Once one gets wrong it is not easy to debug (even stress testing wouldn't catch the latter two mistakes). Of course these are contestants' faults but I am pretty sure that these happened (and so it was never like "10 minutes with computer") for many people. Also, it might be good to have a kind of syntax checker (preferably in the html), though this is arguable.

          Sorry for criticizing you too much... I like E's idea itself and appreciate your work.

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

          We heavily discussed TL and ML in this problem and he even considered removing the problem just because of this.

          Atcoder when given a cool algorithm problem: There is this minor issue and I can’t stand it. Let’s reject.

          Atcoder when given a trivial math knowledge problem: No data structure knowledge needed, what a great problem!

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

        Well, I think i same quite simple implementations for both B and D. But I'm not sure if thinking on implementing B without trie was worth time spent on it.

        I quite liked problems, they have some balance on thinking/writing you can move in diffrent ways. Probably, only problem looks strange for me is C. fft solution is quite obvious, and most time I spent on this problem was thinking if there is something easier.

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

pairforces

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

Why this code get Wa in problem A???

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

    Sure, don't read by double type, string instead of. Value stored in double is only approximate not exactly.

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

      I know now,tahnk you! Sadly, I waste too much time on it,and solved none of the problems!

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

This contest made me understand the importance of reading "Point Values".I didn't know E had partial score until there was only 20 minutes left...

»
4 years ago, # |
  Vote: I like it -21 Vote: I do not like it

How to solve C? I was trying for half an hour but in vain.

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

I am surprised that rng_58 accepted this problem set... (A: harmful for top ranked contestants, contradicting to him past policy, C: too typical).

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

    What do you mean by harmful for top ranked contestans xd?

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

      I meant this: https://codeforces.com/blog/entry/75163?#comment-592623

      The input format is annoying to process (the number of decimal digits are not fixed, sometimes even no decimal point). The balance between implementation and thinking will then be too implementation-heavy...

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

        I do not understand why you distinguish top ranked contestans here, still don't get what is harmful here and you can omit all implementation problems with:

        long double f;
        cin>>f;
        int a = int(1e9 * (f + 1e-12));
        
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          I just put "for top ranked contestants" according to the link I posted above so please don't put too much weight there.

          I am not sure that always works. Is long double environment independent? Works if no digits after decimal point? I chose to do it in integers rather than to search for specs. (so maybe I'm not a top ranked programming-understander?)

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

    I'm sorry about C being well known. I was cautious about it but testers, coordinator and someone else I asked didn't know such a problem.

    I will defend A though. It's easy and the code is short. I wouldn't use A in div2 contest for sure but AGC is said to be div 0.8 and participants understand real values better. If you used FFT in C, you assumed almost same precision as the one required in A to read easily. And with atcoder scoring, you can conveniently skip a problem and later see if they solve something fast or they get WA.

    As written in the editorial, C++ double has 53 bits of precision, it's enough to precisely represent an integer up to more than $$$10^{15}$$$, that's much more than $$$10^{13}$$$ required in A.

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

      Thanks for the reply.

      As I also solved C by integer calculation it's not the case that I understand floating point numbers very well (I haven't see any rigorous proof for the double precision is enough for such convolution...). I'm still on the side of doubting this A doesn't match AtCoder's policy, though.

      Anyway, I hoped that the input values always had 9 digits after the decimal point, which would make the problem fairly harmless.

      And with atcoder scoring, you can conveniently skip a problem and later see if they solve something fast or they get WA.

      I did. The stats looks dangerous, at least to me.

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

tourist broke the Rating record of Atcoder.

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Can someone tell me why my code TLEs for problem B even though the complexity is O((sum of lengths)*26) https://atcoder.jp/contests/agc047/submissions/15789169

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

For problem B, this was my implementation which gets TLE (19 AC / 7 TLE): https://atcoder.jp/contests/agc047/submissions/15786366

I'm not sure if the time-limit was too tight for hash-based solutions, or if I've implemented it in a much-too-slow way (since editorial does say hashes should pass). Does anyone have a (fast) hash solution or any suggestions for constant optimization of the above which passes?

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Hello Errichto it's a humble request please make a video on fft, how to use them how to build them everything, i tried to run some searches after reading editorial of today's contest of third question. i don't think there is enough material on this, please make a detailed editorial of the concept explaining others questions also based on this.

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

I found that the permutation tree enables one to solve problem F almost without thinking. Of course I couldn't get all details right during the contest, but the point still stands :)

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

    I know that structure (under the name divide-combine tree) and I tried to make sure that it doesn't solve the problem significantly easier. I concluded that it can only simplify the first boring part of the intended solution so whatever. Your code suggests something similar because your dfs function is similar size to my whole solution. Do you do something like $$$dp[node][left/right]$$$ there? If yes, that's fine and I was aware before the contest. If no, please say a bit more about your solution.

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

      I do "given this node in the tree, compute the answers for all starting points inside it, given that if we manage to eat the entire segment and finish at the smallest number, we will spend A outside this segment, and if we manage to eat the entire segment and finish at the largest number, we will spend B outside this segment."

      So it's some kind of DP backwards.

      I'm not entirely sure what are you referring to as the first part of the intended solution, but for me the data structure was instrumental for bringing the search space from quadratic to linear, which was the main idea required to solve the problem in my opinion.

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

        Yup, it's the same dp.

        The first part of the intended solution is basically getting nodes of permutation tree but it's much easier in this problem because we can stop whenever non-monotonic pattern occurs, e.g. children $$$(3,1,4,2)$$$. This makes the implementation easy: starting from any maximal monotonic block, keep expanding alternately with brute force: bottomLeft+topRight and bottomRight+topLeft. Thinking about permutation tree is one of possible ways to prove the amortized linear complexity.

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

Hi Errichto, please help to understand multiplication using FFT. I tried understanding this Your text to link here... but in this , it is taking only one polynomial it is not taking the other one for multiplication. Please help me if i am understanding anything wrong??

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

Can you post solution in Python 3?

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

Well, tourist might hit 4400, and then, whats the next title for him? Atcoder made legend and king just for him......

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

    Tourist should change AtCoder handle to Kong so that his profile page calls him King Kong instead of King tourist...

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

I tried to AC T1,but failed,help! this is my code

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

    Edit your comment and put the code in <.spoiler></spoiler> (remove the dot).

    If you want to round real value to integer, use round(x) or even better llround(x). Just casting to int is literally billion times worse (because it always rounds down).

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

@Errichto Please create Editorial on your Youtube channel for this contest. Problems are really very interesting.Thank you

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

I am new to coding and I cannot understand how Trie has been implemented in the question B editorial. Can someone please guide me through it?

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

    Find any tutorial on trie and read it.

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

    If you are a beginner, don't jump to data structures needed for tough problems right now. Be comfortable in easy problems first.