FLOORI4 - Editorial

[xcwgf666]

Problem link : contest practice

Difficulty : Easy

Pre-requisites : AD-hoc problems experience

Solution :

At first, the formula for the sum of 1⁴+2⁴+…+n⁴ is n(1+n)(1+2n)(-1+3n+3n²)/30. The level of the problem is EASY, so the formula can be found on the internet.

At second, there are only sqrt(n) different values for [n/i] over all i from 1 to n. This fact is also well known and can be proved.

So, the solution is as follows:

• We iterate all the different values of [n/i].
• For each such value X we can calculate the maximal range [L; R] such that for each i, L <= i <= R, [n/i] = X. When we have a segment, we can calculate an answer for it, using the above formula in O(1).

So the total time complexity is O(sqrt N) per a test case.

Setter’s solution: link

Tester’s solution: link

[filmwalams]

Why the same implementation in python gave TLE, but worked in java,cpp ?

[Gaurav_Rai]

I always observe that for last 3-4 problems in each contest we don’t find a single Python submission and for editorial approach also we get tle, so codechef should increase time limit for Python or provide a Python solution or remove Python option for such problem statements.

[ahmed1ossama13]

Links to the setter and tester solution don’t work!

[krooonal]

all right … the part I got stuck at was dividing it by 30. Since M is given as input, what is the guarantee that the modulo inverse of 30 exists ?

[achaitanyasai]

@krooonal You can play a trick as : just multiply ‘m’ with ‘30’.Say this as M.i.e M=m*30;now perform modulo using M.Finally divide the anser with 30.Refer my solution : http://www.codechef.com/viewsolution/4803010 .POWER() method in my solution

[pranjalranjan]

@achaitanyasai You just changed my life. Now i think that my whole life has been a lie man, i spent 4 hours thinking about that and still coudn’t get a right answer Thanx for the help, man!

[nisargshah95]

It seems out of 696 solutions for this problem, none were in Python 2/3. This does not seem fair…

[nisargshah95]

I agree. They should make python (and all other slow languages for that matter) TLs flexible depending on the algo expected for the problem.

[mohit22995]

Can anyone please explain how does the “multiplying m by 30 and then dividing result by 30” approach works??

[d1d5]

Can anyone please explain what is wrong with this approach? And isn’t the formula for (1^4)+(2^4)+…, while we need to calculate (1^4)(n/1) + (2^4)(n/2) +…?

#include<stdio.h>

#include

#include<math.h>

using namespace std;

int main()

{

unsigned int n_of_tst,i,j,nbyi;

long double n,m,ans[3000]={0};
cin>>n_of_tst;

for(i=0;i<n_of_tst;i++)
{
	cin>>n>>m;
	for(j=1;j<=n;j++)
	{
		nbyi=n/j;
		ans[i]=ans[i]+(pow(j,4)*nbyi);
	}
	
}
for(i=0;i<n_of_tst;i++)
{
	cout<<(int)ans[i]%(int)m<<endl;
}

return 0;

}

[naren65]

Same solution in Ruby gives TLE. Codechef team should seriously consider increasing the time limit for slower languages for such problems.

[devuy11]

1 upvote from my side. I had no idea before hosting this problem that python would time out. Setter(Myself) and Tester did wrote C++ code and believed that the multiplier would work fine! I personally do not like changing problem/time limit in running contest after it had a lot of submissions. If i had seen this issue when only 5/10 users had tried then i would have definitely changed the time limit. I thought it was not a serious issue and the guys will enjoy handling overflows in C/Java/C++.I apologize and promise that all my easy/simple/cakewalk problems will be solvable in python.Thanks

[tonynater]

When we say that a=b mod m (0<=b<m) we mean that the remainder when a is divided by m is b. This is equivalent to saying that there exists an integer q such that qm+b=a. We are trying to prove that if n/k=x mod m (0<=x<n, k>0), then n=xk mod mk and 0<=xk<mk. We know that n/k=x mod m is equivalent to saying that there exists a q such that qm+x=n/k. Multiplying by k, we see that (qk)m+xk=n. We see that this is equivalent to the statement we are trying to prove(with q’=qk and remainder xk), and that additionally 0<=xk<mk since 0<=x<m.

[bewithaman]

I did the same in Python and was getting TLE…!!!

[abcdexter24]

A good answer, thanks @devuy11

[szilard]

@achaitanyasai Can you please explain why this trick works from a mathematical point of view?

[rgaut_89]

Can some please explain me this
“there are only sqrt(n) different values for [n/i] over all i from 1 to n”

eg: n= 25
I get different values of floor(n/i), they are as follows

i
1 25,
2 12,
3 8,
4 6,
5 5,
6 4,
7 3,
8 3,
9 2,
10 2,
11 2,
12 2,
13 1,
14 1,
…
so different values are 25, 12, 8, 6, 5, 4, 3, 2, 1

[war_lock]

@tonynater when we say a=b mod m we mean that when b is divided by m ‘a’ is the remainder???

[johri21]

@szilard see tonynater explaination…below