We will hold AtCoder Beginner Contest 284.
- Contest URL: https://atcoder.jp/contests/abc284
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230107T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Nyaan, yuto1115
- Tester: Kodaman, m_99
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Looking forward to participate
How to solve E?
solve it 1 hour on paper then write brute force and oeis it in 10 minutesE is not G...may I ask how did you implement A262973?no, I found this by printing frequencies of Bhttps://atcoder.jp/contests/abc284/submissions/37841145Avoid divisions: multiply each summand by n!/2. Denominator will be reduced with either (n — q) or (n — 1 — q). n!/q! can be precalculated.
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
Any hint for F?
I use Hash. But I pass 3 min after the contest. Stuck at E too long!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
https://atcoder.jp/contests/abc284/submissions/37848937
maybe two kmp? but I still don't solve it.
Thanks, will revisit string algorithms
Use string hashing and manually put in indices. Submission for reference Submission
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 ?
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
I used Rabin-Karp algo
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!
Have you checked collisions? There are many WA so I doubt it but still.
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
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}$$$.
I can assure that hashing is appropriate for F.
You can check out my submission.
I think it's very unlikely that there will be 30+ anti-hash test-cases.
Btw, one problem in the submission is low array-space.
By increasing the
const int N, the WA count drops to 1. submissionHow to solve G ?
for some reason I kept trying pollard－rho for D and continuously failed... bruh
Same man :'), while it was just brute force. LMAO
dude we are sad pathetic people :(
It's alright, we all mess up. We will reach our goal eventually. Good Luck!!
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.
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}$$$.
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 .
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.
Do you find sin(x) in O(sin(x))? You simply need to take square root. No need to enumerate anything.
Thank you all I understood my mistake.
ABC 250 D is similar to ABC 284 D: https://atcoder.jp/contests/abc250/editorial/3937
In editorial of D , how is it guaranteed that p and q will both be prime numbers?
Read the problem statement carefully.
The testcases are set such that p and q will be prime numbers)
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?
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.
its given
Getting only one test case wrong on problem F (02_large_00.txt). How can I view this test case?
wait for some days , then the test cases would be uploaded here https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
Ohk thnx ✌️
Burnside for Ex is too classical I think, and not interesting.
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.
What is answer for Input n=8 in Problem D
n cannot be 8 according to the problem statement. p^2*q but p and q has to be distinct prime numbers.