It would be great if someone gives a detailed solution to this question.
Thanks in advance
2 Likes
Can anyone tell me how to optimize this code for ROBOTS problem.
link to the code : hLBIs2 - Online C++0x Compiler & Debugging Tool - Ideone.com
I think sorting canāt help because you need to take two numbers consecutively and the order cannot be changed for Xi elements you need to lookup for maximum differences , store consecutive differences into another array and then sort it and then find which maximum difference came from which two indexes
For people stuck in ROBOTS problem, try:
For ith query (l, r), you have to assume it started from 0,0 and then encountered lth character.
Example:
1
4 1
4123
2 3
Correct ans:
-0.50000000 0.86602540 [Move 60 deg (0.5 0.866) + Move 120 deg (-1 0)]
Any addition based approach might give: 0 1.7320508
Fault in logic is assuming you can just subtract the l-1 x,y coordinates.
But keep in mind your direction has changed too. The entire vector space is at some dā degree to original. So, you would need to convert final coordinates to original vector space by doing inverse degree calculation.
Tips:
For printing correct accuracy:
double PI = 2*acos(0) double cos60 = cos((60.0 * PI)/180.0); double sin60 = sin((60.0 * PI)/180.0); printf("%.8f %.8f\n", x, y);
I was quite tired after codechef certification exam, so I didnt participate, but after looking at the questions for about 20 min, these are my initial ideas.
Biggest Restaurant : Simply take two smallest on the ends?
Robots in Chefland: This is just Segment Tree, maintain the displacement vector for each segment of moves
Challenge Day: if the increase in skill level could not be negative, two segment trees would cut it, one on the challenges for the compos, and one on the people for challenges. Now the problem is, increase in skill can be negative hence we dont know if the person will skip the compo or notā¦ Iāll think about it
Black and White: Basically maintain LCAās so that we can find the u-v path easily. Also add some augmentations like number of black nodes from root-node path for each node, ptr to prev black node etc. This kind of reduces the problem to a P&C one. Havenāt coded it out yet, but seems doable.
Expected Number of Customers:
After fiddling about for \text{n = 1,2,3,4}, I kind of get an FFT vibe from this. I think its kind of some divide and conquer + FFT, but thats just an intuition.
Overall seems pretty good, but implementation might be a pain. Will try tomorrow.
Good questions this time though.
Just my approach to the problem BIGRES.
The area of a trapezium is 0.5x(Sum of parallel sides)x(Distance between them).
Now, after a bit of inspection of the formula, I realized that it is the same as the sum of the areas of the two right triangles with the base as āDistance between themā and height as the heights of each of the parallel sides.
After this, you can change the question as finding the maximum area of all the triangles thus formed. Now the x-axis is not going to change and we can only put restaurants of height āhā at different points.
The greedy approach would be to give the maximum height to the point where the difference between the next and the previous point is maximum, as that height element is going to form triangles with those two points. Therefore we can make an array of the distance between Point_i-1 and Point_i+1 for each i from 1 to N, and sort them.
Note that the x coordinate of Point_0 is taken as that of Point_1 and similarly Point_n+1 is taken as Point_n for maintaining the boundary conditions. [As the first and the last height elements will only form one triangle.]
Then we just need to sort the array of heights and for each index, multiply the corresponding heights and base lengths.
3 Likes
I used shoe lace formula for calculating polygonā¦but yes my code is correct for difference 1 only can anyone tell me how can i modify to get ac
link to my solution
1 Like
take the value of n then declare the array
well tring ROBOTS is where u go wrong lol 
u must have tries questions before 
To calculate area of trapeziuem in very simple way use Shoelace Formula
Since N, M is small, you can do brute force. Try for all - n < dr < n, -m < dc < m
and calculate error.
Error: Difference between original & translated new matrix + Values in original which are not translated but are 1.
I donāt understand how solving 1 problem and then sleeping is literally enough to bring me up a starā¦
1 Like
SIGSEGV is caused by some exception, like divide by zero, array index out of bound etc.
check your loop. Like you have declared your array of size n i.e. your indexes will be in range 0 to n-1, but in 5th line inside your loop, you are accessing index n (when i = n-1 & you are trying to access arr[i+1] ), which is not possible (called array index out of bound exception).
You deserve >=5 stars
Great approach brother 
2 Likes
Donāt need to do trapezium.
As the question asks for 2s, this is the triangle portion of the points (abs(h1-h2) * abs(x1-x2) + (min(h1,h2) * abs(x1-x2) * 2) for the area for each 2 point segment (two triangles on top of each other make a rectangle).
From this, you can see the best answer will have the biggest h1,h2 for the biggest difference in x1, x2. Sort x1 and x2 based on the distance they have from their neighbors, and height by accending order. The closest x1 and x2 should be matched with he smallest heights. This pair array should then be sorted by x, and the cordinates should be entered into the function above to find the individual areas.
Yep, the switch statement is wrong in implementation. I see youāve picked up the cases correctly, but 0 does not always give +2. It changes the angle. So the first ā1ā would give +1, the second 1 would give 0, the third one would give -1, etc (going around the circle). The different cases change the angle, so you need a %6 somewhere.
else {
if (l != 0) {
x = (cx[r] - cx[l-1]);
y = (cy[r] - cy[l-1]);
}
else {
x = cx[r];
y = cy[r];
}
This bit is kinda wrong. I donāt know why youāre minusing the x (itās a variable value each time).
The sin and cos calculation are also only ever 0.8, -0.8, 0.5, and -0.5 so you can save on time there.
However, in this question you also had to memoize previous calculations which I failed to do.