 # ADDFRAC - Editorial

#1

EASY

### EXPLANATION

Consider plotting the points (yi,xi) on the plane. For each point i we add, we wish to know what is the point j, along with which the point i makes the maximum slope line when the two points are joined. Note that this point lies on the convex segment of the points p0…p(i-1). Thus we keep a convex segment of the points on a stack as we proceed. When we encounter the point i, we keep popping points from the stack till the current point does not form a concave segment with the last two
points on the stack. The last point on the stack is the optimal j we were looking for. Push i on the stack, and proceed. Since each point is pushed/popped at most once, we have a linear time algorithm.

#2

To think about this problem geometrically was such a nice innovation. Too bad the editorial doesn’t attempt to properly explain the solution. But still the idea itself deserves an upvote.

#3

Can anyone explain the editorial properly?
I am not able to grasp the explanation of the editorial.

#4

What’s wrong with this code? It always say time limit exceeded. The answer in editorial is beyond my scope, somebody could explain it?

``````import java.util.*;
public class Main
{
public static int euclidean(int a,int b)
{
if(b==0)
return a;
else
return euclidean(b,a%b);
}

public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int num=sc.nextInt();

int Ar1[]=new int[num];
int Ar2[]=new int[num];
sc.nextLine();
for(int i=0;i<num;i++)
{
String s[] = sc.nextLine().split("/");
Ar1*   = Integer.parseInt(s);
Ar2*   = Integer.parseInt(s);
}

for(int i=0;i<num;i++)
{
int finalx=0,finaly=0;
double oldvalue=0;int value1=0,value2=0;
for(int j=i;j<num;j++)
{
value1+=Ar1[j];
value2+=Ar2[j];

if(((double)value1/(double)value2)>=oldvalue)
{
oldvalue=(double)value1/(double)value2;
finalx=value1;
finaly=value2;
}
else
{
break;
}

}

int c=euclidean(finalx,finaly);
finalx=finalx/c;
finaly=finaly/c;

System.out.println(finalx+"/"+finaly);
}

System.out.println(" ");
while(t>1)
sc.nextLine();
}

}

}``````

#5

can’t we use dynamic programming?

#6

The problem seems interesting. Is it possible to get a detailed editorial @admin​:diamonds: 