LUCASTH - Editorial

time limit for this problem must be 1 or 2 sec(hard problem). because i see some approach that not considered for this problem.

1 Like

To illustrate what is talked about in gorre_morre’s post here is two images showing an image plot of f(n,k)%p!=0 (where black is true, white is false) with n along the vertical axis and k along the horisontal axis.


Here p=5 shows the Seirpinski fractal/gasket (large image, so expand at will):

Click to view

p=5, sierpinski


And here p=101 shows the detail of a single element, where we note that all base triangles are the identical:
p=101, detail

We’re interested in the number of black pixels in some row. So just by finding the answer for the base triangle we can use the structure of the Sierpinski fractal to compute the answer for an arbitrary row. Specifically this involves interpreting the row index as a number in base p to see how many base triangles there is for a given index.

2 Likes

@userhacker no 1 sec is also too long … it should be 0.000…inf…1 nano seconds

Using OEIS, I noticed the given example was a sequence produced by Stirling Numbers of the First Kind. I then looked for formulas for Stirling numbers. I used FFT for numbers less than 100K.

Can anyone explain this line “Let Δ(f)Δ(f) be the number of nonzero coefficients of ff, then Δ(f⋅g)=Δ(f)Δ(g)Δ(f⋅g)=Δ(f)Δ(g), since gg has degree <p−1<p−1 and ff has nonzero coefficients only on xi(p−1)xi(p−1) terms.”

I mean how is delta(f.g) =delta(f)*delta(g) ?

how can you be sure that after multiplying f and g, no coefficient will become zero. I understand that all terms will have different powers. But that does not stop a coefficient becoming 0 mod p.

Can u please how did u calculate the ans by calculating N%p rows? I too saw some trinagles bt wasnt able to deduce anything

@algmyr about time complexity of this if N was equal P/2 now what is time complexity of this?!

@userhacker The case n=p/2 is not actually the worst case, it’s more like n=p/\sqrt{2} (so about 70000 for the largest allowed prime). And as for time complexity: Finding the correct row is quadratic in n\,\textrm{mod}\,p. Finding the number of triangles for a given row is more or less O(\log(n)), at least small enough to be insignificant.

If you are clever about searching from the top or bottom depending on what row you want, you ended up passing the test cases, although you can easily devise cases that kills such a solution, like n=p/\sqrt{n}.

@gorre_morre said time complexity so according that i choose N=49999 and p=99991 then we have
O(min(49999,49992)^2)=O(49992^2)=O(2499200064) and we have 4 test case?

i think you getting close to main solution. in main solution we find a general pattern for every N according to p,p^2,p^4,p^8,p^16 ,… <10^501. just this have one exception for that we need calculate F(value of exeption,p) with FFT. this is fastest way. your way is near it.
link text

That time complexity is correct asymptotically, but the actual number of operations is a bit different since we work on a triangle. The point where working from above is more expensive is a bit lower down than half the triangle, essentially the horizontal line that cuts the triangle in two pieces with the same area.

This way is nowhere near the one expected one complexity wise. It’s just pure luck that this approach ends up working with the test cases, n\,\textrm{mod}\,p never ended up close to the worst case for this algo.

check this test case for TLE:
4
49999 99991
, 49999 99971
, 49999 99989
, 51999 99991

goodby man.good luck.

On my laptop just the first case takes like 6 seconds (pypy) which wouldn’t by itself be a TLE, since pypy for some reason has the same time multiplier as python, 5x. I think your test could potentially actually work if run on the server. However 50k is not the worst case, as stated. From what I measured on single cases, in (p,time) pairs: (50000,6.3), (60000,9.1), (70000,36.7), (80000,14.3), (90000,7.6)

Please if anyone could help…

For example, suppose that p=7, and f=x^{12}+2x^{6}+3, and g=x^5+x. Then
f only has non-zero coefficients on x^{6i} terms. g has degree <6.

fg = x^{17}+x^{13}+2x^{11}+2x^{7}+3x^{5}+3x

\Delta (fg) = 6 = 3 \times 2 = \Delta(f) \Delta(g).

2 Likes

If possible can u please provide a mathematical proof for this : delta(f.g) =delta(f)*delta(g)

Thank you

A careful proof will be a maze of notation, and probably not helpful. Perhaps a sketch will help.

f is the sum of \Delta(f) terms, each of the form a x^{r(p-1)}.

g is the sum of \Delta(g) terms, each of the form b x^s, with s<p-1.

When calculating fg, we multiply each of the \Delta(f) terms by each of the \Delta(g) terms, and add the products together.

How many terms are there in fg? Certainly no more than \Delta(f)\Delta(g). But could there be less? No, because each of the products is non-zero, and all the powers of the resulting x^{r(p-1)+s} are different.

1 Like

Got it!!!

Thank you so much!!!

How can a coeffiecient be 0?
For convinience lets say q=p-1.
See f is a polynomial with terms of multiple of power q,g is a polynomial with degree<q;
Lets say i is the power of a term in result,so i will be (j*q)+k where j denotes x^(jq) power if present in f,k denotes x^k power if present in g;

So as u can see ,i will always be distinct,so for each mul we get a distinct term,so for the coefficient to be 0,(a*b)modp should be 0(a is coefficient in f,b in g),which is not possible if a!=0,b!=0,p->prime

1 Like