Отправлено: 16.04.22 17:38. Заголовок: №4742 (26.67) Ошибка в алгоритме

Здравствуйте!

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

Предложенный в решении алгоритм не учитывает вариант, что некоторые запросы могут начинаться одновременно. Если такие запросы начинаются где-то внутри окна, то ничего страшного не происходит, потому что они только увеличивают счетчик. Но если эти запросы идут все окно и начинаются с левой границы (начало окна k), то тогда алгоритм дает сбой, потому что он высчитывает время работы между соседними началами запросов

 
 maxTime += abs(t) - abs(data[i-1]) 
 

Соответственно нам нужно минимум 2 запроса, которые начинаются одновременно с левой границы и идут все окно. При первом запросе алгоритм инкрементирует счетчик и запоминает его значение в переменной prev, на втором запросе счетчик снова увеличивается и считается прошлый период времени (время между двумя началами), но поскольку начала находятся в одной точке (равны), то время работы будет равно нулю. А поскольку два запроса идут весь интервал, то счетчик никогда не будет меньше или равен найденному минимальному значению и время обработки запросов так и останется равно нулю.

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

Чтобы убедиться на практике в чем проблема и понять как это работает, достаточно расширить данные двумя отрезками

 
 data.extend([START, -END]) 
 data.extend([START, -END]) 
 

Алгоритм выдаст 5766 одновременных запросов обрабатываемых 0 мс, когда на самом деле их 5767 и обрабатываются они так же 22703 мс.

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

 Отправлено: 16.04.22 18:23. Заголовок: Если в окне не будет..

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

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

Как не посмотри, не лучший алгоритм предложен в решении.

В соседней задаче с поиском максимума (66) вроде эти проблемы не проявляются из-за максимума, но все равно остается проблема сортировки одновременных концов и начал вызовов.

 Отправлено: 16.04.22 20:34. Заголовок: Согласен с вашими до..

Согласен с вашими доводами. Тут проблема, конечно, только в одновременности двух или нескольких событий. Изменил решение на такое:

 with open('26-66.txt') as f: 
   N, START = map(int, f.readline().split()) 
   END = START + 24*3600*1000 
   data = [] 
   for i in range(N): 
     t0, t1 = map(int, f.readline().split()) 
     if t0 == START: t0 -= 1 
     if t1 == END: t1 += 1 
     if t1 == 0: t1 = 10**10 
     data.extend( [t0, -t1] ) 
  
 data.extend( [START, -START] ) # учесть первый интервал 
 data.append( END )             # учесть последний интервал 
 data.sort( key = abs ) 
  
 nProc = 0 
 allChunks = [] 
 for i, t in enumerate(data): 
    nProc += 1 if t >= 0 else -1 
    if START <= abs(t) <= END: 
      if allChunks and allChunks[-1][1] == abs(t): 
         allChunks.pop() 
      allChunks.append( (nProc, abs(t)) ) 
  
 minProc, maxTime = 10**10, 0 
 for i in range(len(allChunks)-1): 
    nProc, t = allChunks[ i] 
    if nProc < minProc: 
       minProc = nProc 
       maxTime = 0 
    if nProc == minProc: 
       maxTime += allChunks[i+1][1] - t 
  
 print( minProc, maxTime )

 Отправлено: 19.04.22 20:24. Заголовок: Поляков, здравствуйт..

Поляков, здравствуйте! Спасибо за ответ.

Я не очень понимаю, почему Вы полагаетесь на сортировку из библиотеки, она же ненадежная для этой задачи.

Например, у меня выходит следующее:

 
 arr = [-1, 1, -1] 
 arr.sort(key=abs) 
 print(arr)	#[-1, 1, -1] 
 

В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму.

Еще непонятно, зачем Вы уменьшаете начала и продлеваете концы по границам окна:

 
 if t0 == START: t0 -= 1 
 if t1 == END: t1 += 1 
 

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

 Отправлено: 20.04.22 12:24. Заголовок: beep пишет: В таком ..

beep пишет:

цитата:

В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму.

Приведите пример, пожалуйста.

цитата:

Если идет группировка вроде уже не обязательно формировать начальное значение счетчика до окна

Согласен.

 Отправлено: 21.04.22 14:41. Заголовок: Поляков, извините, м..

Поляков, извините, пожалуйста, моя невнимательность. Я не заметил, что Вы группируете в чанки по модулю, поэтому и последовательность неважна. Я идеи из старого алгоритма, где отдельно начала и концы перенес на новый, а тут уже просто узловые точки идут. Вопрос снимается, спасибо за ответы!