title: Time complexity on simulation exercise
body: <p>I am having a problem with algorithm complexity, I have attempted the solution below thinking it was easy when i forgot to take into account the time constraint. I have added my code below which I'm not even sure the complexity of. I am curious to see what the <code>O(N)</code> or <code>O(K)</code> solution would be. If someone could help out with this it would be appreciated greatly.</p>
  
  <pre><code>Time Limit: 1 second
  </code></pre>
  
  <p>There are K seats available, each represented by a physical seat at a point around a circle. The K+1 people are also initially standing at points around the circle. Points on the circle are labelled clockwise from 1 to N, such that point 1 immediately follows point N. No two people will be initially standing at the same point, and no two chairs will be at the same point. </p>
  
  <p>Each second, all the people who are still standing do the following (simultaneously):</p>
  
  <blockquote>
    <ul>
    <li><p>If the person is standing at the same point as an empty chair, the person will sit down in it.  </p></li>
    <li><p>Otherwise, the person will step one place clockwise around the circle to the next point. If the person was previously at point i (with i &lt; N), the person will now be at point i+1. If the person was previously at point N, the person will now be at point 1. </p></li>
    </ul>
  </blockquote>
  
  <p>Since there are K+1 people, eventually all K seats will be taken and the one person remaining without a seat. The person sitting in the first seat in the circle will have the best place. (The ‘first’  seat in the circle is defined as the first seat clockwise from point 1.)</p>
  
  <p>Your task is to determine who will be in the first seat and who will be the person left standing up.</p>
  
  <p>Input 
  N and K.<br>
  K space-separated integers representing the points at which there are chairs, in increasing order. Hence, the first chair in this list will be the first seat<br>
  K+1 space-separated integers representing the points of people, in increasing order. The people are numbered from 1 to K+1 by their position in this list.</p>
  
  <p>1 ≤ N ≤ 1000000<br>
  1 ≤ K ≤ 100000</p>
  
  <p>Output<br>
  Person in the first seat<br>
  Person left standing    </p>
  
  <pre><code>Sample   
  
  Input   
  10 3   
  2 5 8   
  3 4 6 8   
  
  Output   
  3   
  1   
  </code></pre>
  
  <p><img src="https://i.imgur.com/XjqCPuL.png" alt="initial config"></p>
  
  <p>In the first second, the fourth person (at point 8) will immediately sit down on the chair beneath them. The other three people will move one place around the circle. In the next second, the second person (now in position 5) will sit down on the second seat. The first and third people will continue walking around the circle until the third person reaches position 2 and sits down, leaving the first person with no chair to sit in. </p>
  
  <pre><code>while(standing != 1)
  {
      for (int i = 0; i &lt; K + 1; i++)
      {
          if (sitting[i] == 0)
          {
              people[i]++;
  
              if (isSitting(people[i], chairs,i)) //this function checks if the current person is at a chair
              {
                  sitting[i] = 1;
                  standing--;
              }
  
              if (people[i] &gt; N)
              {
                  people[i] = 1;
              }
          }
      }
  
      }
     standingPerson = indexOf(sitting,K+1 ,0);
  </code></pre>
  
  <p>This attempt times out on almost all of the test input, only passing 8/30 cases.</p>
  
  <hr>
  
  <p>Here is some code using an O(k) solution suggested by another user. Transferred to c++</p>
  
  <pre><code>    int seat1 = chairs[0], best = -1, accum = 1;
  int unlucky[] = {0, -1};
  
  for (int pos; pos &lt; K + 1; pos++) {
      if (people[pos] &lt;= seat1) {
          best = people[pos] + 1;
          accum -= 1;
      } else
          break;
  }
  
  if (accum &lt; 0) {
      unlucky[0] = accum;
      unlucky[1] = 1;
  }
  
  int i = K, j = K - 1;
  while (i &gt;= 0 &amp;&amp; people[i] &gt; seat1) {
      if (chairs[j] &gt;= people[i]) {
          accum += 1;
          j -= 1;
      } else {
          accum -= 1;
          i -= 1;
      }
      if (best == -1 &amp;&amp; accum == 0) {
          best = i + 2;
      }
      if (accum &lt; unlucky[0]) {
          unlucky[0] = accum;
          unlucky[1] = i + 2;
      }
  }
  fprintf(out_file, "%d\n%d", best, unlucky[1]);
  </code></pre>