$1.$ Problem Statement

In a wedding party, there are $$n$$ children invited and all of them are seated in a line. Initially,

few candies were distributed to each child and some children were missed and did not

receive any candy. Our aim is to give an equal number of candies to each child.

In order to do so$,$ we can choose each move such that any $$m m n$)$ children can

pass one of their candy to their neighboring child at the same time.

Given an integer array $$candies$$ representing the number of candies with each child from left

to right on the line, return the minimum number of moves to make all the children have the

same number of candies. If it is not possible to do$,$ return $-1.$

Constraints:

$$ n $==$ candies.length

n

candies$[$i

Requirements

$1.$ Formulate an efficient algorithm using Greedy Technique.

$2.$ Implement the above problem statement using Python $3\mathrm{.}7$

$3.$ Read the input from a file $($inputPS$09.$txt$)$ and Print the sequence of events and total

time taken for the entire queue of processes to be executed.

$4.$ You will output your answers to a file $($outputPS$09.$txt$)$ for each line.

$5.$ Perform an analysis for the features above and give the running time in terms of

input size: n along with justification.

Example Input:

Sample Input:

Input will be taken from the file$($inputPS$09.$txt$).$

Sample Input Example

A$.$ candies $=[1,0,5]$

B$.$ candies $=[0,3,0]$

C$.$ candies $=[0,2,0]$

Sample Output:

Display the output in outputPS$01.$txt$.$

A$.3$

Explanation: $($This is only written for your understanding, you don$$t need to

output the steps$)$

$1$st move:

$2$nd move:

$3$rd move:

B$.2$

Explanation: $($This is only written for your understanding, you don$$t need to

output the steps$)$

$1$st move:

$2$nd move: $12-->0=>111$

C$.-1$

Explanation: $($This is only written for your understanding, you don$$t need to

output the steps$)$

It is impossible to make all three children have the same number of candies.

Note that the input$/$output data shown here is only for understanding and

testing, the actual file used for evaluation will be different

$1.$ Deliverables

$1.$ PDF document designPS$09\_.$pdf detailing your design approach and time

complexity of the algorithm and alternate solutions.

$2.[$Group id$]\_$Contribution.xlsx mentioning the contribution of each student in terms of

percentage of work done. Columns must be $$Student Registration Number$,$Name$,$

$$Percentage of contribution out of $100\%.$ If a student did not contribute at all, it will be

$0\%,$ if all contributed then $100\%$ for all.

$3.$ inputPS$09.$txt file used for testing

$4.$ outputPS$09.$txt file generated while testing

$5..$py file containing the python code. Create a single $*.$py file for code. Do not fragment

your code into multiple files.

$6.$ Zip all of the above files including the design document and contribution file in a

folder with the name: $[$Group id$]\_$A$2\_$PS$09.$zip and submit the zipped file in canvas.

$7.$ Group Id should be given as Gxx where xx is your group number. For example, if your

group is $26,$ then you will enter G$26$ as your group id$.$

$3.$ Instructions

$1.$ It is compulsory to make use of the data structure$($s$)/$ algorithms mentioned in the

problem statement.

$2.$ Ensure that all data structure insert and delete operations throw appropriate messages

when their capacity is empty or full. Also ensure basic error handling is implemented.

$3.$ For the purposes of testing, you may implement some functions to print the data

structures or other test data. But all such functions must be commented before

submission.

$4.$ Make sure that your read, understand, and follow all the instructions

$5.$ Ensure that the input, prompt and output file guidelines are adhered to$.$ Deviations from

the mentioned formats will not be entertained.

$6.$ The input, prompt and output samples shown here are only a representation of the

syntax to be used. Actual files used to evaluate the submissions will be different.

Hence, do not hard code any values into the code.

$7.$ Run time analysis is to be provided in asymptotic notations and not timestamp based

runtimes in sec or milliseconds.

$8.$ Please note that the design document must include:

a$.$ The data structure model you chose with justifications

b$.$ Details of each operations with the time complexity and reasons why the chosen

operations are efficient for the given representation

c$.$ One alternate way of modeling the problem with the cost implications.

$9.$ Writing a good technical report and well documented code is an art. Your report cannot

exceed $4$ pages. Your code must be modular and quite well documented.

$10.$ You may ask queries in the dedicated discussion section. Beware that only

hints will be provided and queries asked in other channels will not be

responded to$.$

Instructions for use of Python:

$1.$ Implement the above problem statement using Python $3\mathrm{.}7+.$

$2.$ Use only native data types like lists andDeliverables

PDF document designPS$09\_$