Efficient Algorithm ?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Efficient Algorithm ?

  1. #1
    Join Date
    Apr 2009
    Posts
    14

    Efficient Algorithm ?

    Hi,

    I am trying to find a O (n) algorithm for this problem but unable to do so even after spending 3 - 4 hours. The brute force method times out (O (n^2)). I am confused as to how to do it ? Does the solution requires dynamic programming solution ?

    http://acm.timus.ru/problem.aspx?space=1&num=1794

    In short the problem is this:

    There are some students sitting in circle and each one of them has its own choice as to when he wants to be asked a question from a teacher. The teacher will ask the questions in clockwise order only. For example:

    5
    3 3 1 5 5

    This means that there are 5 students and :

    1st student wants to go third
    2nd student wants to go third
    3rd student wants to go first
    4th student wants to go fifth
    5th student wants to go fifth.

    The question is as to where should teacher start asking questions so that maximum number of students will get the turn as they want. For this particular example, the answer is 5 because

    3 3 1 5 5
    2 3 4 5 1

    You can see that by starting at fifth student as 1st, 2 students (3 and 5) are getting the choices as they wanted. For this example the answer is 12th student :


    12
    5 1 2 3 6 3 8 4 10 3 12 7

    because

    5 1 2 3 6 3 8 4 10 3 12 7
    2 3 4 5 6 7 8 9 10 11 12 1

    four students get their choices fulfilled.

    Thanks

    Ravi

  2. #2
    Join Date
    Apr 2009
    Posts
    14

    Re: Efficient Algorithm ?

    Don't worry guys ! I found out the O (n) algorithm.

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: Efficient Algorithm ?

    Quote Originally Posted by vsha041 View Post
    Don't worry guys ! I found out the O (n) algorithm.
    Lets compare solutions.

    If there are N students there are N possible starting positions.

    You need an array of N counters each representing a starting position.

    By knowing a student's position at the table you also know which starting position satisfies this student's preference.

    So you only have to visit each student once and increment the counter associated with his/her preference. Afterwards the starting position with the largest count is the one that satisfies most students.

    Visiting each students is an O(N) process. Updating a counter is a table look-up so it's an O(1) process. This means the overall complexity will be O(N).

    One can note that compared with the brute force O(N^2) algorithm this one has lower time complexity but at the cost of more memory (the N counters). In the original problem formulation N can be 10^5 at the most so this O(N) algorithm is still feasible.

    Since the students don't have to be visited in any particular order they can be visited at the same time. It means the algorithm can be run in parallel and if there are N processors it will be O(1).
    Last edited by nuzzle; January 14th, 2011 at 10:14 AM.

  4. #4
    Join Date
    Apr 2009
    Posts
    14

    Re: Efficient Algorithm ?

    Thanks nuzzle ! The O(n) algorithm I used is exactly same as yours. Thanks for your time.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center