can someone explain in a easier way how to solve this problem . I cant understand the editorial. specifically the part where it says "ai iterations in i-th step is equal to doing ai mod (n - i) iterations (0-based numbering). That is less than n". Please help.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Solution : As n<=100, we can just have a O(n^2) algorithm (here n^2 denotes the overall complexity which is iteration*deletion). We can just start by the first leader which is 1, and delete the element on the (leader_index+a[i])%(current amount of people) position.
We can just use a vector and erase that element and set the leader to the next element.
Why are we taking mod : If a_i is greater than the current amount of people in the group then we are just revisiting the same people again and again so we take mod by the total number of people to have the exact element in 1 step.
The tutorial is just saying that the total number of people after the i-th step is (n-i) (0 based), because we have removed one element in 1 step.
Please, inform me if something is unclear. =)
Got it. But someone told me that you cant use vector for deletion because the erase function in vector takes o(size) time.
True. But because $$$n$$$ is at most $$$100$$$, we are free to use it.
We can use a set too. It will improve our deletion time to $$$O(lg(n))$$$, but then the time to access any element will be increased to $$$O(n)$$$, giving us the overall complexity of $$$O(n^2)$$$ again.
i see ...i got your solution to this problem but now i am curious how editorial is solving it without any deletions. If you have time can you elaborate how is editorial planning to do this? i think they are taking a bool vector and counting the number of ones or something like that.
In the editorial, they are saying that, let the pointer represent the current leader. The bool array tells you whether the i_th person is eliminated or not. If i_th index is 0, then the i_th person is eliminated and vice versa. Now we move the pointer forward until the count of ones becomes equal to (a[i]%mod) (So that we count the people who are still alive). When the count of ones becomes equal to a[i]%mod, it means we have to eliminate the current person. So, we make the boolean array of the i_th person equal to 0. Which shows that he is eliminated. And we move the pointer to the person ahead. As the group is standing in a circle, whenever our pointer goes to n+1, we move it to 1 again. :)
Thanks bro...i finally implemented it on my own. Took me 2 whole days to actually do it. But you taught me very nice things. Thanks a lot.
NP ;)