$(20$ points$)$ You are given a positive integer $k$ and an array $A[1..n]$ that

stores $n$ possibly non$-$distinct integer scores in the range $1,100.$ The

scores in A are stored in non$-$decreasing order. The scores are conceptually

divided into $k$ groups such that for iin$[1,k],$ group i consists of scores in

the range $(100\frac{i-1}{k},100\frac{i}{k}].$ Your task is to design an algorithm to

count the number of scores in group i and store the count in the array

$G[1..k].$ The count for group i should be stored in the entry $G[i].$ Your

algorithm cannot directly access $A[j]$ for any jin$[1,n]$ or $G[i]$ for any

iin$[1,k].$ Instead, it can only access and$/$or modify A and $G$ using the

following three functions:

Init$(G)$ : It initializes all entries of $G$ to zero in $O(k)$ time.

Compare $(i,j)$ : For $i,$jin$[1,n],$ it compares $A[i]$ and $A[j]$ and re$-$

turns true if $A[i]$ and $A[j]$ belong to the same group, otherwise false.

This takes $O(1)$ time.

Increase$(j,x)$ : For jin$[1,n],$ it finds the index $i$ of the group that

contains $A[j]$ and adds $x$ to $G[i].$ This function takes $O(1)$ time.

Your task is to design an algorithm with the following running time re$-$

quirements. Explain its correctness and analyze its running time. $($Note:

A correct answer to $(2)$ will get you all $20$ points, so you don't have to do

$(1)$ if you are certain about your answer to $(2).)$

$(1)(10$ points$)$ Design an algorithm that runs in $O(klogn)$ time.

$(2)(10$ points$)$ Design an algorithm that runs in $O(klog(\frac{n}{k}))$ time.

Hint: Let $x_i$ be the size of group i for iin$[1,k].$ Subject to $x_1+x_2+$

dots$+x_k=n,$ the product $x_1*x_{2}cdots{x}_k$ is maximized when $x_i=\frac{n}{k}$

for all iin$[1,k].$