Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Looking forward to participate

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

»
4 года назад, скрыть # |
 
Проголосовать: нравится 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

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Any hint for F?

»
4 года назад, скрыть # |
← 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!

»
4 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

How to solve G ?

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
← 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.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится +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.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is answer for Input n=8 in Problem D