### Errichto's blog

By Errichto, 22 months ago,

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

 » 22 months ago, # |   +14 Grand contests have a rated range of 1200~inf i guess.
•  » » 22 months ago, # ^ |   +6 Thanks, corrected.
•  » » » 22 months ago, # ^ |   +16 In contest page, its still showing "Rated range: Everyone is rated"
•  » » » 22 months ago, # ^ |   0 please Make video tutorial for this round
 » 22 months ago, # |   -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?
•  » » 22 months ago, # ^ |   +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 :)
•  » » » 22 months ago, # ^ |   +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.
•  » » » » 22 months ago, # ^ |   +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
 » 22 months ago, # |   +84 Wow. Errichto is back at making contest.
 » 22 months ago, # | ← Rev. 2 →   0 In the contest page it is written Rated range: Everyone is rated.What does it mean?
 » 22 months ago, # | ← Rev. 3 →   -126 [DELETED]
 » 22 months ago, # | ← Rev. 2 →   -34 deleted
•  » » 22 months ago, # ^ |   0 There is a 23-hour difference in their start time.
 » 22 months ago, # | ← Rev. 5 →   -63 !
 » 22 months ago, # |   -36 Why just 1200++ ? Its rated for everyone as per Atcoder .
 » 22 months ago, # |   +12 why the duration shrinks？
•  » » 22 months ago, # ^ |   +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.
 » 22 months ago, # |   +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.
•  » » 22 months ago, # ^ | ← Rev. 2 →   -17 Can you reschedule doubts session after CF Round 663 DIv2 for DIv2 participants.
•  » » » 22 months ago, # ^ |   -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
•  » » » » 22 months ago, # ^ |   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.
 » 22 months ago, # |   0 Hoping to have a GREAT contest!
•  » » 22 months ago, # ^ |   +1 It must be!
•  » » 22 months ago, # ^ |   -20 orz
 » 22 months ago, # |   0 good luck all))
 » 22 months ago, # |   -41 Solved A and B but the round is not rated for me. My luck always.
 » 22 months ago, # |   -135 For problem A, I'm getting WA on test case 5 and TLE after test case 5here is my codeany help would be appreciated!
•  » » 22 months ago, # ^ |   +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.
•  » » » 22 months ago, # ^ |   +20 ah thank you! I should have asked the question later.
 » 22 months ago, # |   +11 is this contest have pair?
 » 22 months ago, # |   -18 Thanks god it wasn't rated for me
 » 22 months ago, # |   +144
•  » » 22 months ago, # ^ |   +42 As long as topics and solutions are completely different, I don't see anything wrong there.
•  » » » 22 months ago, # ^ |   +64 Nothing wrong with it, I just thought it was funny. :P
 » 22 months ago, # |   +37 Good problem set. How to solve C?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +41 Logarit and FFT.
 » 22 months ago, # |   -10 Nice contest Errichto!, anyway problem C can be solved in O(nsqrt(p))?
 » 22 months ago, # |   +44 I think Problem C is quite standard. The idea behind problem E is really interesting. How to solve it?
 » 22 months ago, # |   +110 It seems nowadays codeforces has better problems than atcoder...
•  » » 22 months ago, # ^ |   -31 Can you elaborate? What's there other than C being known?
•  » » » 22 months ago, # ^ |   +75 Maybe that's just me, I can't say anything about DF, but I find AB uninteresting :(
•  » » » 22 months ago, # ^ |   +146 A: boring.B: write trie(or hashes)C: write FFTE: 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.
•  » » » » 22 months ago, # ^ | ← 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.) codevector in(n); vector> paths(n); // extra thing needed in B for(int who = 0; who < n; ++who) { string& s = in[who]; cin >> s; reverse(s.begin(), s.end()); // extra thing needed in B int node = 0; for(char ch : s) { paths[who].push_back(node); // extra thing needed in B if(child[node][ch-'a'] == 0) { child[node][ch-'a'] = nxt++; } node = child[node][ch-'a']; } is_end[node] = true; }  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)
•  » » » » » 22 months ago, # ^ |   +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.
•  » » » » » 22 months ago, # ^ |   +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?)
•  » » » » » 22 months ago, # ^ |   +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.
•  » » » » » 22 months ago, # ^ |   +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!
•  » » » » 22 months ago, # ^ |   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.
 » 22 months ago, # |   +13 pairforces
•  » » 22 months ago, # ^ |   +5 Atpair Grand Contest
 » 22 months ago, # |   0 Why this code get Wa in problem A??? Code/* { AuThOr Gwj */ #pragma GCC optimize(2) #include #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a>a #define R2(a,b) cin>>a>>b #define int LL using namespace std; const int INF=0x3f3f3f3f; typedef pair mp; /*} */ int n,a[200000+20]; double a_[200000+20]; int all[65][65]; signed main(){ fastio; R(n); LL res=0; rb(i,1,n){ R(a_[i]); a_[i]*=1000000000.0; a[i]=(LL)(a_[i]); int A,B; A=B=0; while(a[i]%5==0){ a[i]/=5; A++; } while(a[i]%2==0){ a[i]/=2; B++; } // cout<=18&&j+B>=18){ res+=all[k][j]; } } all[A][B]++; } cout<
•  » » 22 months ago, # ^ | ← Rev. 2 →   -8 Sure, don't read by double type, string instead of. Value stored in double is only approximate not exactly.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 I know now,tahnk you! Sadly, I waste too much time on it,and solved none of the problems!
 » 22 months ago, # | ← 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...
 » 22 months ago, # |   -21 How to solve C? I was trying for half an hour but in vain.
 » 22 months ago, # |   +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).
•  » » 22 months ago, # ^ |   +8 What do you mean by harmful for top ranked contestans xd?
•  » » » 22 months ago, # ^ |   -8 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...
•  » » » » 22 months ago, # ^ |   -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)); 
•  » » » » » 22 months ago, # ^ |   +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?)
•  » » 22 months ago, # ^ |   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.
•  » » » 22 months ago, # ^ |   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.
 » 22 months ago, # |   +1
•  » » 22 months ago, # ^ |   0 Thank you! nice explanations.
 » 22 months ago, # | ← Rev. 2 →   +61 tourist broke the Rating record of Atcoder.
 » 22 months ago, # |   -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
 » 22 months ago, # | ← Rev. 2 →   0 For problem B, this was my implementation which gets TLE (19 AC / 7 TLE): https://atcoder.jp/contests/agc047/submissions/15786366I'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?
•  » » 22 months ago, # ^ |   +21 link.I noticed that you use 2 small moduli instead of 1 big, but there may be other differences as well.
•  » » » 22 months ago, # ^ |   0 Not making 26 hashes for each prefixes helped me. Thanks.
•  » » 22 months ago, # ^ |   +13 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
•  » » 22 months ago, # ^ |   +11 Hashes should quite easily pass (say, one third of TL) so likely you can implement them better.
 » 22 months ago, # |   -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.
•  » » 22 months ago, # ^ |   +84 Not enough material on FFT, really?
 » 22 months ago, # |   +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 :)
•  » » 22 months ago, # ^ |   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.
•  » » » 22 months ago, # ^ |   +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.
•  » » » » 22 months ago, # ^ |   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.
 » 22 months ago, # |   -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??
•  » » 22 months ago, # ^ |   -38 ЫАЫАЫАЫААЫАЫА
 » 22 months ago, # |   -15 Can you post solution in Python 3?
•  » » 22 months ago, # ^ |   0 You can filter submissions by language.
•  » » » 22 months ago, # ^ |   0 Thanks
 » 22 months ago, # |   +3 Well, tourist might hit 4400, and then, whats the next title for him? Atcoder made legend and king just for him......
•  » » 22 months ago, # ^ |   +79 Tourist should change AtCoder handle to Kong so that his profile page calls him King Kong instead of King tourist...
 » 22 months ago, # | ← Rev. 4 →   +10 I tried to AC T1,but failed,help! this is my code Spoiler#include #define int long long using namespace std; int n,t,f,ans; double a; map,int> m; signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lf",&a); int b=a*1000000000; t=f=-9; while(b%2==0) { b/=2; t++; } while(b%5==0) { b/=5; f++; } ++m[make_pair(t,f)]; } for(auto i:m) for(auto l:m) if(i.first.first+l.first.first>=0&&i.first.second+l.first.second>=0) { if(i
•  » » 22 months ago, # ^ |   +8 Edit your comment and put the code in <.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).
•  » » » 22 months ago, # ^ |   0 Thank you so much.
 » 22 months ago, # |   0 @Errichto Please create Editorial on your Youtube channel for this contest. Problems are really very interesting.Thank you
 » 21 month(s) ago, # |   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?
•  » » 21 month(s) ago, # ^ |   -8 Find any tutorial on trie and read it.
•  » » 21 month(s) ago, # ^ |   -6 If you are a beginner, don't jump to data structures needed for tough problems right now. Be comfortable in easy problems first.
 » 21 month(s) ago, # |   -16 Very very hard round it was.