2

i am wasting whole day in this problem...

 1 year ago
source link: http://codeforces.com/blog/entry/109096
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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.

2 hours ago, # |

← Rev. 2 →  

0

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. =)

  • 2 hours ago, # ^ |

    Got it. But someone told me that you cant use vector for deletion because the erase function in vector takes o(size) time.

    • 41 minute(s) ago, # ^ |

      Worst Case (N*N iteration * N (delete) ---> O(N^3). Since maximum value of n is 100. Time Complexity is O(10^6). Which is enough for this problem.

    • 33 minutes ago, # ^ |

      ← Rev. 2 →  

      +1

      True. But because is at most , we are free to use it.

      We can use a set too. It will improve our deletion time to , but then the time to access any element will be increased to , giving us the overall complexity of again.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK