Hi
I've explained the solution for problem D from today's contest in my YouTube video.
It was a nice math based problem, solved using tries. Code link will be added later in the video description.
I will be adding the video for C tomorrow.
If you want daily updates about my channel,
1. Subscribe to the channel.
2. Follow the facebook page.
Cheers!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
I don't think you strictly need tries. Just store occurrences of each prefix. But your solution would consume less memory. Solution without tries: 29900524
Can you explain your approach for the problem C
For problem C, you just need to note that for each vertex the number of possible distinct gcds is small. This is because for each descendant of the root, the possible gcds divide lcm(a_root, a_child_of_root). Now keep that for each vertex, and in dfs, update that accordingly and call the dfs for the children.
Thanks rachitiitr! It was wonderfully explained.
Welcome.