Hello Guys,
This is part two of Unofficial Editorials February Challenge, containing editorials for CARPTUN, BROCLK and POINPOLY.
For other editorials, refer CHEFCHR, CHEFPTNT and PERMPAL [here][1].
Problem : [CARPTUN][3]
Problem Difficulty: Easy
Problem Statement:
Given Delay times of N toll booths, speed of cars S, number of cars C and the distance D between each tol booth, determine the delay between First car and Last car.
Solution:
Observation:
Sub-task 1:
In this case, There are only two cars, so we can actually simulate the whole process in O(CN) without getting TLE.
Let time[i][j] denote exit time of ith car from jth toll.
For first car, Time taken by car to exit from ith toll is time[0][i] = time[0][i-1]+D/S+A[i]. (Taking into account the time taken to reach toll and Delay time at ith tunnel.)
For subsequent cars, Time taken by car to exit ith toll would depend upon exit time of previous car. Specifically, time[C][i] = max(time[C][i-1]+D/S, time[C-1][i])+A[i]
Above relationship because when we reach the toll, there might be a car already there, in which case we’ll have to wait till that car completes its delay time. If there’s no car when we reach there, we can start the delay time immediately.
Final Answer would be time[C-1][N-1] - time[0][N-1].
Refer [this][4] solution for details.
Subtask 2:
Now, Number of cars is upto 1e6, which means that O(CN) solution will time out. We need some observations to speed up our solution to O(N).
Observation:
- Speed and Distance given in problem is irrelevant.
Proof: Since each car has to cover D*(N-1) distance to reach from first toll to last toll, all cars will have the same delay D*(N-1)/S due to driving, thus, it would be better to simply ignore this delay. - The Final Answer will be max(A[i])*(C-1).
Proof: Suppose a car can now move with the infinite speed. Now, the only time each car has to wait will be max(A[i]). This can be proved easily, thus left as an exercise.
Hence, we get the answer max(A[i])*(C-1) in O(N) time.
[Link][5] to my solution.
Link to my
[6].
### Problem : [BROCLK][7]
#### Problem Difficulty: Easy-Medium
#### Prerequisites: Matrix exponentation, Trigonometric identities.
### Problem Statement:
Given a clock with one hand (Don't know how Chef see the time from it :P), which got broken, now move by fixed angle. We are not given this angle, but Length of hand L, and Distance of tip of hand from X-axis after one second.
We are supposed to find distance of tip of hand from x-axis.
### Solution:
We are given following scenario.
![alt text][8]
**Time for some Math**:
We can see that the triangle in figure is a right triangle. Time for [Trigooonmetry][9].
We can see that for given position, $\sin (90 - \theta) = \cos \theta = D/L$.
We can easily see that After T seconds, The angle moved by hand is $T*x$, and thus, Our final answer would be $L*\cos(T*X)$.
Now, How to calculate $\cos(T*X)$ ??
### Important property: $\cos(N*X) = 2*\cos(X)*\cos((N-1)*X) - \cos((N-2)*X)$
Proof can be found [here][10]
### When T is upto $1e6$:
In this case, we can Run a loop from 1 to T aand compute the answer. Refer [this][11].
### When T is around $1e18$:
Now, we cannot run a loop as we will get TLE.
But, observe the above Recurrence Carefully. Doesn't is resemble the well know Fibonacci Sequence. So, we will calculate the Tth value of above recurrence in $O(logT)$ time, getting 100 points, in same manner as we Calculate Nth Number of Fibonacci Sequence, as explained [here][12].
Not so easily, Because above explanation is lacking one point regarding use of Modular inverse, as well as Formation of matrix , which i have intentionally left to as to give you a chance to try even after the contest. DO GIVE A TRY BEFORE RUSHING TO SOLUTION. (This very point kept my solution hanging till the last day.)
[details=Click to view]
Fraction $d/l$ can also be represented as $d*modInverse(l)$ and also, modulo can be taken at every step to avoid overflow.
[/details]
Link to my
[13].
Problem : [POINPOLY][14]
Problem Difficulty: Medium
Problem Statement:
Given a convex polygon consisting of N points, Find and print floor(N/10) points lying strictly inside it or report if it’s impossible.
Solution:
Geometry is scary, Polygon is no less. But, Triangle are our friends in this problem. Wanna know how??
See the following picture.
![alt text][15]
This way, We have divided our polygon into a set of triangles. Now, For a triangle, it is easy to determine it a point lie strictly inside the tirangle, using following property. If ABC is the riiangle and P is the point to be checked, then
Area(ABC) = Area(PAB)+ Area(PAC)+Area(PBC) And, None of these three triangle should have area 0 (P will lie on border of triangle in this case.)
Now, Coming to implementing part, How to select points to be checked??
The answer is, Process all triangles one by one and Check points around the corners of triangle (In all 8 directions) and add them to answer if they lie inside.
Now Comes the crux of Solution. Triangle is a convex polygon, thus, all points lying inside a triangle will be adjacent to each other. This means that we can continue adding points into our answer bag, until we get sufficient number of points or there aren’t anymore points inside triangle, thus we will move to next triangle.
We must check surrounding 8 cells, and insert into answer bag, as well as search its neighbors (Just like moving inside a grid). Make sure not to process any point twice.
And that’s all, 100 points to you because you have solved and implemented this solution.
For implementation details, refer my
[16].
This brings end to part 2, Hope you liked them.
Feel free to post your queries.
Enjoy coding!!
[1]: https://discuss.codechef.com/questions/122738/unofficial-editorials-february-long-challenge-part-1
[3]: https://www.codechef.com/problems/CARPTUN
[4]: https://www.codechef.com/viewsolution/17322856
[5]: https://www.codechef.com/viewsolution/17360209
[6]: https://www.codechef.com/viewsolution/17360209
[7]: https://www.codechef.com/problems/CHEFPTNT
[8]: https://discuss.codechef.com/upfiles/BROCLK.png
[9]: https://www.khanacademy.org/math/trigonometry/trigonometry-right-triangles/intro-to-the-trig-ratios/a/opposite-adjacent-hypotenuse
[10]: https://math.stackexchange.com/questions/1017668/prove-that-cosnx-2-cosn-1x-cosx-cosn-2x
[11]: https://www.codechef.com/viewsolution/17411630
[12]: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
[13]: https://www.codechef.com/viewsolution/17412144
[14]: https://www.codechef.com/problems/PERMPAL
[15]: https://discuss.codechef.com/upfiles/poly.png
[16]: https://www.codechef.com/viewsolution/17246330
)
Yeah, sad but had to swallow my pride 