ADDFRAC - Editorial

editorial
, , ,
1

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.

2 Likes
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.

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

}

}
5

can’t we use dynamic programming?

1 Like
6

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

2 Likes