Hi. I invite you to AtCoder Grand Contest 047.

- Contest URL: https://atcoder.jp/contests/agc047
- Start time: Sunday, August 9, 12:00 UTC
- Duration: 140 minutes
- 6 Problems, 300-700-800-1000-(800+1000)-2200
- Writer: Errichto
- Rated range: 1200+

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.

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

Thanks, corrected.

In contest page, its still showing "Rated range: Everyone is rated"

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?

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

It was still rng_58 who accepted and rejected problems :)

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.

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

Wow. Errichto is back at making contest.

[DELETED]

deleted

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

why the duration shrinks？

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

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

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

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.

Hoping to have a

GREATcontest!It must be!

orz

good luck all))

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

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!

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:

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.

ah thank you! I should have asked the question later.

is this contest have pair?

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

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

Good problem set. How to solve C?

Logarit and FFT.

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

I think Problem C is quite standard.

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

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

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

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

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.

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

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

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

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.

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)

Just a small note about problem D:

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.

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

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

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.

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!

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.

pairforces

Atpair Grand Contest

Why this code get Wa in problem A???

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

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

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

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

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

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

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

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:

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

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

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

editorial: https://atcoder.jp/contests/agc047/editorial

stream: https://www.twitch.tv/errichto

tourist broke the Rating record of Atcoder.

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

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?

link.

I noticed that you use 2 small moduli instead of 1 big, but there may be other differences as well.

Not making 26 hashes for each prefixes helped me. Thanks.

I optimized your code a little to insert only those values in map, which are to be used in the answer. It passes in ~2.5s.

https://atcoder.jp/contests/agc047/submissions/15791797

Hashes should quite easily pass (say, one third of TL) so likely you can implement them better.

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.

Not enough material on FFT, really?

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

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

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.

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??

ЫАЫАЫАЫААЫАЫА

Can you post solution in Python 3?

You can filter submissions by language.

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

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

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

SpoilerEdit 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).Thank you so much.

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

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?

Find any tutorial on trie and read it.

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