chokudai's blog

AtCoder Beginner Contest 284 Announcement
By chokudai, history, 16 months ago, In English

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!

  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to participate

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for F?

→ Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you checked collisions? There are many WA so I doubt it but still.

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve G ?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for some reason I kept trying pollard－rho for D and continuously failed... bruh

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you find sin(x) in O(sin(x))? You simply need to take square root. No need to enumerate anything.

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you all I understood my mistake.

        → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    ABC 250 D is similar to ABC 284 D: https://atcoder.jp/contests/abc250/editorial/3937

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of D , how is it guaranteed that p and q will both be prime numbers?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Read the problem statement carefully.

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The testcases are set such that p and q will be prime numbers)

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.

        → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its given

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting only one test case wrong on problem F (02_large_00.txt). How can I view this test case?

→ Reply
»
16 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Burnside for Ex is too classical I think, and not interesting.

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is answer for Input n=8 in Problem D

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n cannot be 8 according to the problem statement. p^2*q but p and q has to be distinct prime numbers.

    → Reply