Сложность времени при симуляции

Question

У меня возникла проблема с сложностью алгоритма. Я попытался найти решение ниже, думая, что это легко, когда я забыл учитывать временные ограничения. Я добавил код ниже, который я даже не уверен в сложности. Мне любопытно узнать, что такое решение O(N) или . Если бы кто-то мог помочь с этим, это было бы очень признательно.

Time Limit: 1 second 

Доступно K мест, каждое из которых представлено физическим сиденьем в точке вокруг круга. Люди K + 1 также изначально стоят в точках по кругу. Точки на круге помечены по часовой стрелке от 1 до N, так что точка 1 сразу следует за точкой N. Ни один человек изначально не будет стоять в одной точке, и ни один из двух стульев не будет в одной точке.

Каждый второй, все люди, которые все еще стоят сделать следующее (одновременно):

• Если человек стоит в той же точке, как пустой стул, человек сядет в Это.

• В противном случае человек переместится на одно место по часовой стрелке по кругу в следующую точку. Если человек ранее находился в точке i (с номером i < N), человек теперь будет в точке i + 1. Если человек был ранее в точке N, человек будет теперь в точке 1.

Поскольку существует K + 1 человек, в конце концов, будут приняты все K мест и один человек оставшийся без места , Человек, сидящий на первом месте в круге, будет иметь лучшее место. («Первое» место в круге определяется как первое место по часовой стрелке от точки 1.)

Ваша задача - определить, кто будет на первом месте и кто будет стоять лицом.

Ввод N и K.
K целые числа в пространстве, представляющие точки, в которых есть стулья, в порядке возрастания. Следовательно, первым председателем в этом списке станет первое место
K + 1 целые числа, разделенные пробелами, представляющие точки людей, в порядке возрастания. Люди пронумерованы от 1 до K + 1 по своей позиции в этом списке.

1 ≤ N ≤ 1000000
1 ≤ K ≤ 100000

Выход
Человек в первом сиденье
Человек остался стоять

Sample 

Input 
10 3 
2 5 8 
3 4 6 8 

Output 
3 
1 

В первую секунду, четвертый человек (в точке 8) сразу садится на стул под ними. Остальные трое будут перемещать одно место вокруг круга. В следующую секунду второй человек (теперь в позиции 5) сядет на второе место. Первый и третий люди будут продолжать ходить по кругу, пока третий человек не достигнет позиции 2 и садится, оставив первого человека без кресла.

while(standing != 1) 
{ 
    for (int i = 0; i < 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] > N) 
      { 
       people[i] = 1; 
      } 
     } 
    } 

    } 
    standingPerson = indexOf(sitting,K+1 ,0); 

Эта попытка срабатывает почти на всем тестовом входе, только проходя 8/30 случаев.

---

Ниже приведено описание кода с помощью решения O (k), предлагаемого другим пользователем. Переведен в C++

int seat1 = chairs[0], best = -1, accum = 1; 
int unlucky[] = {0, -1}; 

for (int pos; pos < K + 1; pos++) { 
    if (people[pos] <= seat1) { 
     best = people[pos] + 1; 
     accum -= 1; 
    } else 
     break; 
} 

if (accum < 0) { 
    unlucky[0] = accum; 
    unlucky[1] = 1; 
} 

int i = K, j = K - 1; 
while (i >= 0 && people[i] > seat1) { 
    if (chairs[j] >= people[i]) { 
     accum += 1; 
     j -= 1; 
    } else { 
     accum -= 1; 
     i -= 1; 
    } 
    if (best == -1 && accum == 0) { 
     best = i + 2; 
    } 
    if (accum < unlucky[0]) { 
     unlucky[0] = accum; 
     unlucky[1] = i + 2; 
    } 
} 
fprintf(out_file, "%d\n%d", best, unlucky[1]); 

Answer 1

Чтобы определить, кто будет на первом месте, нам необходимо подсчитать количество мест/лиц, начиная с первого места в обратном направлении, и остановиться, как только количество людей будет равным количеству мест. Чтобы реализовать это, нам нужен аккумулятор, который увеличивается, когда сиденье встречается и уменьшается, когда человек сталкивается. Остановитесь, когда этот аккумулятор равен нулю.

Чтобы определить, кто будет стоящим лицом, мы могли бы продолжить обновление аккумулятора таким же образом и найти позицию, в которой этот аккумулятор получает свое минимальное значение в первый раз.Для позиции любого человека, где этот аккумулятор не минимален (или когда этот минимум ближе к началу массива, чем какой-либо другой минимум), мы могли бы найти позицию позже в массиве, где этот аккумулятор имеет такое же значение, а это значит, что достаточно места чтобы этот человек сидел.

См. Диаграмму ниже для более подробного объяснения. Он отображает значения аккумулятора для всех возможных положений места/человека. Хотя алгоритм обходит входные массивы только один раз, на этой диаграмме показаны значения аккумулятора для этих массивов, пройденных три раза, так что циклическая природа проблемы видна.

Значения для каждого массивов обхода похожи друг на друга. Единственное различие заключается в том, что значения уменьшаются на единицу каждый раз, когда мы приходим к одной и той же точке круга.

Легко заметить, что все значения аккумулятора, кроме одного, имеют следующее свойство: мы всегда можем найти еще одну точку с тем же значением в круге. Это означает, что количество мест и количество лиц между этими двумя точками равны друг другу. Это означает, что каждый человек, начинающий позицию между этими двумя точками, будет также находиться где-то между этими двумя точками: все люди справа уходят от этого интервала и не притворяются, что занимают эти места. Все левые приходят слишком поздно.

Некоторые интересные случаи для интервала между этими равноценными точками: (1) когда интервал пересекает границу массива, (2) интервал между двумя минимальными значениями, (3) очень короткий интервал, когда пустое место находится рядом с человеком или если они находятся в одной точке.

И только одно положение (4), соответствующее последнему минимальному значению аккумулятора (или первое, если мы ищем назад), не имеет этого свойства. Нет никакого смысла с тем же значением справа. Лицо в этом начальном положении останется стоящим.

Вот рабочий код на Python: Ideone link.

def solve(k, s, p): 
    seat1 = s[0] 
    best = -1 
    unlucky = (0, -1) # min(accum), position 
    accum = 1 

    # process all persons between start of the array and the seat #1 position 
    for i, pos in enumerate(p): 
    if pos <= seat1: 
     best = i+1 
     accum -= 1 
    else: 
     break 

    if accum < 0: 
    unlucky = (accum, 1) 

    # process all seats/persons in reverse direction 
    i = k 
    j = k-1 
    while i >= 0 and p[i] > seat1: 
    if s[j] >= p[i]: # a seat 
     accum += 1 
     j -= 1 
    else: # a person 
     accum -= 1 
     i -= 1 

    if best == -1 and accum == 0: 
     best = i+2 # +1 because indexing starts with 0 & +1 because of pre-decrement 

    if accum < unlucky[0]: 
     unlucky = (accum, i+2) 

    return (best, unlucky[1]) 


print(solve(3, [2,5,8], [3,4,6,8])) 

Поскольку каждое из мест/лиц проверяется только один раз, сложность времени - O (k).

Answer 2

Прежде всего давайте упростить эту проблему, думая таблицы как два circular buffers. Один для стульев и один для людей. Можно сказать, что в буфере присутствуют стулья «C», люди «P» и пустые места «E».

Так предполагая, что мы говорим, что кольцевой буфер начинается с 1, ваш пример может быть переписан в виде

E C E E C E E C E E 

E E P P E P E P E E 

Вашего текущим решения будет в худшем случае будет O(N*K). Представьте себе такую ​​конфигурацию, как:

P P E E E E E E E 

E E E E E E E E C 

Ваш алгоритм решает вышеупомянутое путем смещения буфера людей семь раз. И вы реализуете сдвиг, проходя через всех людей и перемещая их по отдельности. Таким образом, ваш алгоритм делает сдвиги O(N) (размер стола), и каждая смена включает в себя перемещение всего O(K) людей на одно место. Таким образом, O(N*K). Хотя, это, я думаю, очень pesimistic верхняя граница, и вы будете намного быстрее в среднем.

---

Я думаю, что хороший O(K) может быть реализован с помощью двух указателей. Указатель на буфер пользователя и другой указатель на буфер стула. Идея состоит в том, чтобы пройти через два буфера отдельно и соответствовать ожидающему человеку с доступным стулом. Идея состоит в том, что всякий раз, когда вы видите стул, если есть человек, который ждет вас, вы можете сопоставить его с этим стулом. Если нет человека, ожидающего, то вы добавляете стул в очередь доступных стульев. Если после того, как мы пройдем через оба буфера, есть доступные стулья и доступные люди, тогда мы знаем, что это люди, которые должны пройти через точку 1, чтобы найти стул, и мы можем сопоставить их с доступными стульями, последний ожидающий человек с первым доступным стулом.

В дополнение к двум указателям вы можете использовать две очереди для отслеживания доступных стульев и ожидающих людей. Ниже представлена ​​псевдокодная версия решения.

queue<Person> personQueue; 
queue<Chair> chairQueue; 
int cptr=0, pptr=0; 

while(cptr < K || pptr < K+1) 
    if (cptr >= K) { 
     //no chairs ahead of us only behind us 
     personQueue.addAllRemainingPersons() 
    } 
    else if(pptr >= K+1 || chair[cptr] < person[pptr]) { 
     // the currently pointed at chair is at a lower position 
     // than the pointed at person, 
     // so we match this chair with a waiting person instead 
     match(personQueue.back, chair[cptr]); 
     cptr++; 
    } 
    else { 
     //add person to the waiting-for-chair queue 
     personQueue.push_back(person[pptr]); 
     pptr++; 
    } 
} 
// at this point we have a situation with many chair in front of many persons 
// for example 
// CCCCPPPPP 
// This we solve by matching the last person with the first chair 
// until only one is left 
while(!cQueue.empty()) { 
    match(personQueue.back, chairQueue.front); 
} 

Определение, кто является человеком, который получает сидит в первом кресле может произойти в функции матча, где у вас есть достаточно информации, чтобы быть в состоянии сказать. Человек, который остается стоящим, единственный, кто не нашел места (единственного, для которого мы не будем называть матч).