Понимание более быстрого подхода к решению этого вопроса?

Question

Постановка задачи дается в problem и является s следующим образом: -

N студенты скучают в компьютерном классе, чтобы они смотреть смешные видео клипы на YouTube.

Сайт содержит K популярных клипов с номерами от 1 до N. Когда просматривается видеоролик , на странице отображается список похожих видеороликов.

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

Напишите программу, которая определяет для каждого учащегося, что видеоклип он будет наблюдать на M-й минуте класса.

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

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

int N = in.nextInt(), K = in.nextInt(), M = in.nextInt() - 1;//Reading input 

    int log = Integer.numberOfTrailingZeros (Integer.highestOneBit (M)) + 1; 

    int [][] next = new int [K][log + 1]; 

    int [] start = new int [N]; 
    for (int i = 0; i < N; i++) 
     start [i] = in.nextInt() - 1; 

    for (int i = 0; i < K; i++) 
     next [i][0] = in.nextInt() - 1; 

    for (int i = 1; 1 << i <= M; i++) 
     for (int j = 0; j < K; j++) 
      next [j][i] = next [next [j][i - 1]][i - 1]; 

    for (int i = 0; 1 << i <= M; i++) 
     if (((1 << i) & M) > 0) 
      for (int j = 0; j < N; j++) 
       start [j] = next [start [j]][i]; 

    out.print (start [0] + 1); 
    for (int i = 1; i < N; i++) 
     out.print (" " + (start [i] + 1)); //writing output 

Как мы можем эффективно решить проблему/не столкнуться с проблемой поиска циклов? Или Как приведенный выше код решает проблему?

Answer 1

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

У вас есть простая матрица преобразования. В строке i у вас будет один 1 - по индексу видео, следующего за номером видео i, и все остальные элементы будут равны 0. Возьмите эту матрицу и поднимите ее до m-1 - й степени, и вы получите матрицу преобразования, которая показывает, какое видео вы будете смотреть на m-й минуте, если вы начали с видео i. Это также объясняет, почему автор решения вычитает 1 из ввода для M после его чтения.

Answer 2

Приведенный выше код игнорирует cicles. Он использует метод динамического программирования снизу вверх, подобный методу быстрого экспонирования. Он использует следующую матрицу для хранения следующей позиции каждого ученика после шагов 1, 2, 2^2 и т. Д. Это работа 3-го для. Затем, в 4-м, он строит M в двоичном формате. Таким образом, если M = 2^3 + 2^0, место каждого ученика можно вычислить, сначала вычисляя позицию после 2^0 минут, назначая это в качестве базовой позиции, а затем вычисляя положение через 2^3 минуты от этого нового должность.

Если вы посмотрите на информацию о быстром экспонировании, вы увидите, что это пространство памяти для памяти O (N log (M)) не требуется, так как есть только один запрос, вы можете вычислить конечную позицию, делая «быстрый шаг за шагом ".