ADDFRAC - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

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.

1 Like

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

1 Like

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.

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

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[i]   = Integer.parseInt(s[0]);
    Ar2[i]   = Integer.parseInt(s[1]);
}


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();
}

}

}

can’t we use dynamic programming?

//