UEMP02 - Editorial

editorial
, , , ,
1

PROBLEM LINK :

[Contest][1]

Probelm Code : UEMP02

Panel Members

Problem Setter:[Sintu Kumar][2]

Problem Tester:[Sintu Kumar][3]

Contest Admin:[Sintu Kumar][4]

DIFFICULTY:

EASY

PREREQUISITES:

Sample,Input Processing , Basic Mathematics,Mathematical Formulation

PROBLEM:

In a school there are N student .On the occation of annual function for each Si th
where 1<=i<=N student givent Ti tasks and difference between tasks of two consecutive students are same and (i+1)the student must get more task than ith student.
School have M number of task. Your task is find out whether task distribution is possible or impossible.

EXPLANATION:

This is the problem based on arithmetic progression. Using Arithmetic Progression Sum this problem will be solved. Here Given that difference between task of each two consecutive student is same. So, the difference between task will be common difference D.

Here it is also mention that (Si+1)th student get more task than Si th student .

So let’s A be number of task assigned to 1st student.

2nd will get A+D number of task.

3nd will get A+2*D number of task.

…

So… on Nth Student will get *A+(N-1)D number of task.

Total number of Task will be = A + A+D +A+2*D +…+*A+(N-1)D

Total Task = (N/2)(2A+(N-1)*D) .

So check for all possible value of A and D. whether Given no of task Match of Not.

if for any combination of A and D match than Task Distribution Possible otherwise Impossible.

Basic C++ Code:

int main() {

int n,m;

cin>>n>>m;

bool isPossible=false;

for(int a=1;a<=100;a++){

   for(int d=1;d<=100;d++){

      long result=(n*(2*a+(n-1)*d))/2;

       if(result==m){

           isPossible=true;

           break;

        }

    }

  if(isPossible)

       break;

}

if(isPossible)

   cout<<"possible"<<endl;

else

    cout<<"impossible"<<endl;

return 0;

}

TIME COMPLEXITY

O(N^2)

SPACE COMPLEXITY

O(1)
[1]: https://www.codechef.com/UEMK2016/problems/UEMP02
[2]: https://www.codechef.com/users/sintuuemisp
[3]: https://www.codechef.com/users/sintuuemisp
[4]: https://www.codechef.com/users/sintuuemisp

2

O(1) solution:

When N is odd…

Let the distribution be [A, A+D, A+2D,… A+(N-1)D]. We know that AP sum is given by N*(2A+(N-1)D)/2, which must be equal to M for a valid distribution. Since N is odd, (N-1) is divisible by 2. Let (N-1) = 2X. Then M = N*(2A+(N-1)D)/2 = N*(A+XD). Thus, the distribution is possible only when M is divisible by N.

Let us try to minimize the sum above. The two variables we can change are A and D. The minimum values for both A and D are 1. Thus, the minimum amount of tasks that can be distributed among N students is given by the distribution [1,2,3,…,N] for the N students, with A=1 and D=1, since 1 is the minimum allowed number of tasks for 1 student. Our provided M value must be >= N*(N+1)/2.

When M is even…

Because N is even now, M = N*(2A+(N-1)D)/2 may or may not be divisible by N.

When N*(2A+(N-1)D)/2 is divisible by N…

Then (2A+(N-1)D)/2 is an integer. Because N is even, (N-1) is not divisible by 2. Hence D must be divisible by 2.

If we try to minimize the sum, we must put A=1 and D=2. Putting these values in the function, we get the minimum value of M as N2.

When N*(2A+(N-1)D)/2 is not divisible by N…

Then (2A+(N-1)D)/2 is not divisible by 2. Thus D must be odd. Rearranging the formula, we get

M = N*A + D*N2/2 - N*(D-1)/2 + N/2

As you can see, the first 3 terms are divisible by N. Thus dividing M by N will leave remainder N/2.

We put A=1 and D=1 to minimize the sum, and we get minimum value of M as N*(N+1)/2.

Final algorithm:

if m is odd

possible if M%N==0 and M>=(N*(N+1))/2

else

possible if (M%N==0 and M>=N2) or (M%N==N/2 and M>=(N*(N+1))/2)

AC solution

3

#include<stdio.h>

using namespace std;
int main() {
int n,m;
cin>>n>>m;
bool isPossible=false;
for(int a=1;a<=100;a++){
for(int d=1;d<=100;d++){
long result=(n(2a+(n-1)*d))/2;
if(result==m){
isPossible=true;
break;
}
}
if(isPossible)
break;
}
if(isPossible)
cout<<“possible”<<endl; <br=""> else
cout<<“impossible”<<endl; <br=""> return 0;
}