Last week ACPC 23 was held, and there are problems to upsolve, so let's discuss problems here.
If there is a problem that you can't solve, maybe ask here and someone will help!
I will start with these problems, C. (Cyclic Paths), G. (Golfing Minimally) I couldn't solve them.
here is the problem set.
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Link?
There isn't an online mirror for it yet.
Lets call the start point as $$$st$$$ and the hole as $$$h$$$.
Considering each segment $$$s$$$, if the ball should bounce in point $$$p$$$ on $$$s$$$ to fall in the hole then if it bounced before $$$p$$$ it will be below the hole and if it bounced after $$$p$$$ it will be above the hole so you can binary search $$$p$$$.
The binary search is not necessary because you can calculate $$$p$$$ using a formula.
If $$$st$$$ and $$$h$$$ have the same distance from $$$s$$$ then $$$p$$$ will be in the middle of the distance between the projection of $$$st$$$ and $$$h$$$ on $$$s$$$. If $$$st$$$ has smaller distance it will be closer to projection of $$$st$$$. So $$$p$$$ will be the center of mass between $$$st$$$ and $$$h$$$ projection on $$$s$$$.
$$$p = st + dis \times \frac{dis_{st}}{dis_{st} + dis_h}$$$
where $$$dis$$$ is distance between the projection of $$$st$$$ and $$$h$$$ on $$$s$$$. $$$dis_{st}$$$ is the distance of $$$st$$$ from $$$s$$$. $$$dis_h$$$ is the distance from $$$h$$$ to $$$s$$$.
After getting $$$p$$$ then you should check if $$$p$$$ is on $$$s$$$ and the segment from $$$st$$$ to $$$p$$$ doesn't intersect with any other segment so is the segment from $$$h$$$ to $$$p$$$.
The Complexity with binary search is $$$O(n^2 . log_2(10^6 \times precession)$$$ and $$$O(n^2)$$$ without binary search.