Rafat's blog

By Rafat, history, 4 years ago, In English

Given the side length of one equilateral triangle and 3 radii R1, R2, R3 which produce 3 sectors inside the triangle. Calculate the area of the triangle which is not covered by the sectors.

My idea is
We can see there can be three cases.

  1. any radius from R1, R2, R3 is greater than or equal to S for which the answer will be Zero
  2. if R1+R2<S and R2+R3<S and R3+R1<S so the answer will be Area of ABC — Area of 3 sectors
  3. if one sector intersects with another...
    For this case, I will check if every pair of circle intersects or not. For this let's denote P as the intersection point. and let's draw a line PT which is perpendicular to the line AB. so from triangle APT and the new sector with an angle 60-Theta so I can get the dashed area from Previous sector Area — (new sector area + triangle APT). with same this approach, I can get the opposite dashed area too which is calculated twice in the addition of sectors area since they intersect. So I'll subtract it from the original sector area.

I'm getting WA with this approach. can you please help me find my mistake :) I'll be glad.
My solution
Problem Link (Problem J)

you can submit your solution for this problem here to check if it gets AC Judge

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By Rafat, history, 5 years ago, In English

Problem: Given a weighted graph G, source node, destination node and a value X. find the shortest route from source to destination.

If there is a path from U to V with cost C, and you choose the path the value of X will change to X=gcd(X,C). So if the new X is less than the cost of next edge you can't pick the next edge. This way you have to find out the shortest path possible.

Node and Edges size can be up to 10^5 and the time limit is 5s. What's the idea to solve this problem??

For better understanding you can find the problem statement Here (Problem F)

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it