### chokudai's blog

By chokudai, history, 14 months ago,

We will hold AtCoder Beginner Contest 284.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +51

| Write comment?
 » 14 months ago, # |   0 Looking forward to participate
 » 14 months ago, # |   0 How to solve E?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 solve it 1 hour on paper then write brute force and oeis it in 10 minutes E is not G...
•  » » » 14 months ago, # ^ |   0 may I ask how did you implement A262973?
•  » » » » 14 months ago, # ^ |   0 no, I found this by printing frequencies of B
•  » » » » 14 months ago, # ^ |   0 https://atcoder.jp/contests/abc284/submissions/37841145 Avoid divisions: multiply each summand by n!/2. Denominator will be reduced with either (n — q) or (n — 1 — q). n!/q! can be precalculated.
 » 14 months ago, # |   0 Non-prime modulo, Jesus Christ. Is there a formula that doesn't involve binomial coefficients? Or I should've had it in my library? :D
 » 14 months ago, # |   0 Any hint for F?
•  » » 14 months ago, # ^ |   0 I use Hash. But I pass 3 min after the contest. Stuck at E too long!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!https://atcoder.jp/contests/abc284/submissions/37848937
•  » » 14 months ago, # ^ |   0 maybe two kmp? but I still don't solve it.
•  » » 14 months ago, # ^ |   0 Thanks, will revisit string algorithms
•  » » 14 months ago, # ^ |   0 Use string hashing and manually put in indices. Submission for reference Submission
•  » » 14 months ago, # ^ | ← Rev. 2 →   +5 Cut the string into half, what do you get ?Reverse the second half, can you apply zfn now ?Then, reverse whole string, and apply zfn again, can you find some relation between these two zfn output arrays ?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +8 Your approach seems interesting! It's not a probabilistic method indeed.PS: I solved it using polynomial hash but it is a probabilistic method. submission
•  » » 14 months ago, # ^ |   0 I used Rabin-Karp algo
 » 14 months ago, # | ← Rev. 4 →   0 I haven't learnt Z Algorithm yet, so I use string hashing for F. But, over half of the tests turned out to be WA. I wonder if hashing was appropriate for this question. My submission. Who can help me and hack it?Upd: Thanks for all of you! I guess my major mistake was setting my array space too low(I forgot it was 2N) and maybe a collision?Upd2: I finally found out my real mistake!
•  » » 14 months ago, # ^ |   0 Have you checked collisions? There are many WA so I doubt it but still.
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 There are a lot of comparisons to be done, so the probability of 1-dimensional hashes colliding is not that small. Hence you should use 2-d hashes.here is my submission: https://atcoder.jp/contests/abc284/submissions/37840173
•  » » » 14 months ago, # ^ |   +8 I think you have linked your problem $E$'s submission rather than $F$ one.Btw I have solved F with single(1D) hash only [submission] but with ${1e9+9}$ mod (As I had heard by Vivek Gupta's stream that testers know which mod and base a person gonna use so they create antihash tests for the same) so probably they have created the antihash tests for ${1e9 + 7}$.
 » 14 months ago, # |   +5 How to solve G ?
 » 14 months ago, # |   0 for some reason I kept trying pollard－rho for D and continuously failed... bruh
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Same man :'), while it was just brute force. LMAO
•  » » » 14 months ago, # ^ |   0 dude we are sad pathetic people :(
•  » » » » 14 months ago, # ^ |   0 It's alright, we all mess up. We will reach our goal eventually. Good Luck!!
 » 14 months ago, # | ← Rev. 2 →   0 Isn't there a mistake in the official editorial for problem D. We need to find the $\sqrt{\frac{N}{q}}$ for a number so the time complexity should be $\sqrt{N}$ rather than cube root if $q$ is small? Take the case where $N$ is close to $9e18$ and $q$ is very small say less than $10$ then $p$ will be a very large prime close to $1e9$. How can we find that using the direct sqrt function? Correct me if I am mistaken somewhere.
•  » » 14 months ago, # ^ |   +1 But in your example $q$ is small, so you will find that searching in $[2, \sqrt[3]{N}]$. The editorial argues that at least one of $p$, $q$ is small, because they can't both be bigger than $\sqrt[3]{N}$.
•  » » » 14 months ago, # ^ |   0 Yes I agree that you will find the smaller $q$ within $O(\sqrt[3]{N}$ but then when we need to find $p$ right. And for finding $p$ we need $O(\sqrt{\frac{N}{q}}$ right? And if $q$ is very small then finding p will give TLE .
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 If q is very small, then your search for p ends up finding q first.Don't just search for p, search for both p and q at the same time.
•  » » » » 14 months ago, # ^ |   0 Do you find sin(x) in O(sin(x))? You simply need to take square root. No need to enumerate anything.
•  » » » » 14 months ago, # ^ |   0 Thank you all I understood my mistake.
•  » » 14 months ago, # ^ |   +1 ABC 250 D is similar to ABC 284 D: https://atcoder.jp/contests/abc250/editorial/3937
 » 14 months ago, # |   0 In editorial of D , how is it guaranteed that p and q will both be prime numbers?
•  » » 14 months ago, # ^ |   +5 Read the problem statement carefully.
•  » » 14 months ago, # ^ |   0 The testcases are set such that p and q will be prime numbers)
•  » » » 14 months ago, # ^ | ← Rev. 4 →   0 I have some experiences about some experiments on this problem. Since, the problem statement said that, "Under the constraints of this problem, it can be proved that the pair of prime numbers p and q such that N = p^2 * q is unique." When I used the deterministic version of Millar — Rabin to ensure whether both p and q are prime, surprisingly it gives WA in some test cases. Is there any proper explanation about such behaviour?In another approach, when I use the Brent's version of Pollard — Rho to factorize N then it gives TLE in more test cases. Once I have read in Topcoder that if N is a square then the algorithm might fail in some test cases to fall in infinite loop. Is there anything which I should know about it?
•  » » » » 14 months ago, # ^ |   0 I don't know about Miller-Rabin, but there are some issues which are addressed on GFG in the end of the article. Hope that helps you.
•  » » 14 months ago, # ^ |   0 its given
 » 14 months ago, # |   0 Getting only one test case wrong on problem F (02_large_00.txt). How can I view this test case?
•  » » 14 months ago, # ^ |   0 wait for some days , then the test cases would be uploaded here https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
•  » » » 14 months ago, # ^ |   0 Ohk thnx ✌️
 » 14 months ago, # |   -8 Burnside for Ex is too classical I think, and not interesting.
 » 14 months ago, # |   +10 For problem F, I use a similar idea as mentioned in editorial but based on a different construction. I build another two strings by concatenating T+inv(T) and inv(T)+T, and then implement z-algorithm to these two strings. It is a pity that, I make a copy of my old codes of z-algorithm, but there is a bug which was not found before. Thanks to this problem for giving me a chance to fix it, and thanks to problem writers.
 » 14 months ago, # |   0 What is answer for Input n=8 in Problem D
•  » » 14 months ago, # ^ |   0 n cannot be 8 according to the problem statement. p^2*q but p and q has to be distinct prime numbers.