FLOORI4 - Editorial

Problem link : contest practice

Difficulty : Easy

Pre-requisites : AD-hoc problems experience

Solution :

At first, the formula for the sum of 14+24+…+n4 is n(1+n)(1+2n)(-1+3n+3n2)/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

11 Likes

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

28 Likes

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

2 Likes

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

7 Likes

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;

}

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

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

1 Like

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

4 Likes

Can anyone explain the sumfour(lli s) function in setter’s solution, what is the logic to find that sum?

#include
#include <stdio.h>
#include <stdint.h>

using namespace::std;

int64_t power_sum(int64_t n, int64_t m)
{
m *= 30;
n %= m;

int64_t ans = 1;
ans = (ans * n) % m;
ans = (ans * (n + 1)) % m;
ans = (ans * (2 * n + 1)) % m;
ans = (ans * ((3 * n * n + 3 * n- 1) % m)) % m;

ans /= 30;
return ans;

}

int main()
{
int T;
scanf("%d", &T);

for (int t = 0; t < T; t++)
{
	int64_t N, M,A,B,C,y,z,ans,x,sum;
	scanf("%lld", &N);
	scanf("%lld", &M);

	 ans = 0;
	 sum=0;
	 x = 1;

	while (x <= N)
	{
		 y = N/x;
		 z = N/y;

		 A = power_sum(z, M);
		// cout<<"a-->"<<A<<endl;
		 B = power_sum(x - 1, M);
		// cout<<"b=="<<B<<endl; 
		 C = (A-B ) % M;
	//	 cout<<"---"<<C<<endl;
		C = (C * y) % M;
	//	cout<<C;

		sum= (sum + C) % M;

		x = 1 + z;
	}

	printf("%d\n", (int)sum);
}

return 0;

}

why wrong answer
in it
#include<stdio.h>
int main()
{
int m,t;
long long n,i,sum=0;
scanf("%d",&t);
while(t–)
{
scanf("%lld%d",&n,&m);
for(i=1;i<=n;i++)
{
sum=(sum+(iiii)(n/i))%m;
}
printf("%lld\n",sum);
}
return 0;
}

why wa
http://www.codechef.com/viewsolution/4816078

What is the proof of this statement that there are only sqrt(n) different values for [n/i] over all i from 1 to n.?

@akshul

HI…

there are at most 2 * sqrt(n) [upper bound] different value for all [n/i] over all i from 1 to n.

As we know if a i number is multiple of n than there are two number i ans (n/i) such that

i * (n/i)=n

As we know here one factor is less than or equal to sqrt(n) and other one factor is greater than or equal to sqrt(n) .

If you are taking i is first factor(less or equal to sqrt(n) ) than i can only have value from 1 to sqrt(n) and other one can have value from sqrt(n) to n;

i.e if a belong to [1 to sqrt(n)] total value that a can have, are sqrt(n).

if n is prefect square than one number will come twice sqrt(n)

that’s why total number sqrt(n)+sqrt(n)-1(to avoid repeating number)

if n is not perfect square of any number than can have at most 2*sqrt(n) factor.

HAPPY CODING

The picture is no longer visible!

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.

11 Likes

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 ?

5 Likes

@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 : CodeChef: Practical coding for everyone .POWER() method in my solution :slight_smile:

6 Likes

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

4 Likes

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

3 Likes