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

Автор Errichto, 4 года назад, По-английски

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.

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

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится +211 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +43 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +84 Проголосовать: не нравится

Wow. Errichto is back at making contest.

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

[DELETED]

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

deleted

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

why the duration shrinks?

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

    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 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

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

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping to have a GREAT contest!

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

good luck all))

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

is this contest have pair?

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

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

Good problem set. How to solve C?

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

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

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

I think Problem C is quite standard.

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

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

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

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

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

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

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

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

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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 года назад, # ^ |
            Проголосовать: нравится +36 Проголосовать: не нравится

          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 года назад, # ^ |
            Проголосовать: нравится +31 Проголосовать: не нравится

          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 года назад, # ^ |
            Проголосовать: нравится +36 Проголосовать: не нравится

          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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

pairforces

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

Why this code get Wa in problem A???

Code
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

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

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 года назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

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

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 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

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

      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 года назад, # ^ |
          Проголосовать: нравится -36 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится

          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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # |
Rev. 2   Проголосовать: нравится +61 Проголосовать: не нравится

tourist broke the Rating record of Atcoder.

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

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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Can you post solution in Python 3?

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

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

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

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

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

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

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Find any tutorial on trie and read it.

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

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