| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
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.
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.
Read about two strings matching : https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
This helpful video for a better understand of the algorithm : https://www.youtube.com/watch?v=V5-7GzOfADQ