Хакерранк «Шерлок Холмс»

  

Уотсон дает Шерлоку массив: A1, A2, ⋯, AN. Он также дает   Шерлок два других массива: B1, B2, ⋯, BM и C1, C2, ⋯, CM , Затем Уотсон спрашивает   Шерлок для выполнения следующей программы:

  for i = 1 to M do
   for j = 1 to N do
     if j % B[i] == 0 then
         A[j] = A[j] * C[i]
    endif
 end do
end do
     

Вы можете помочь Шерлоку и сообщить ему результирующий массив A? Вы должны напечатать все элементы массива по модулю (1000000007).

     

Формат ввода

     

Первая строка содержит два целых числа N и M.   следующая строка содержит N целых чисел, элементы массива A. Следующие два   строки содержат M целых чисел, элементы массива B и C.

     

Формат вывода

     

Печать целых чисел N, элементов массива A после   выполняя программу по модулю (1000000007).

     

Пример ввода

4 3
1 2 3 4
1 2 3
13 29 71
     

Пример вывода

13 754 2769 1508

Если мы грубой силой, время будет упущено. Пожалуйста, предложите способы сделать это эффективным.

import java.math.BigInteger;
import java.util.Scanner;
import java.util.StringTokenizer;

public class SherlockArray {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String line1 = in.nextLine();
    StringTokenizer st = new StringTokenizer(line1, " ");

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    Long[] b = new Long[m];

    String strA = in.nextLine();
    String[] stA = strA.split(" ");
    BigInteger aBI[] = new BigInteger[n];
    for (int ia = 0; ia < stA.length; ia++) {
        aBI[ia] = new BigInteger(stA[ia]);
    }

    String strB = in.nextLine();
    String[] stB = strB.split(" ");
    for (int ib = 0; ib < stB.length; ib++) {
        b[ib] = Long.parseLong(stB[ib]);
    }

    String strC = in.nextLine();
    String[] st3 = strC.split(" ");
    for (int ic = 0; ic < m; ic++) {
        for (int index = b[ic].intValue(); index <= n; index += b[ic]
                .intValue()) {
            aBI[index - 1] = aBI[index - 1].multiply(new BigInteger(st3[ic]));
        }
    }

    for (int ia = 0; ia < n; ia++) {
        aBI[ia] = aBI[ia].mod(new BigInteger("1000000007"));
        System.out.print(aBI[ia] + " ");
    }

}


}
11 голосов | спросил Sharath 26 PM00000020000002831 2014, 14:20:28

4 ответа


3

Более оптимальное решение предполагает отслеживание количества раз, когда происходит B[i].

Это связано с тем, что для каждого кратного B[i]: B[i], 2 * B[i], ..., j * B[i], мы умножаем A[i * j] на C[i]

Это дает следующую информацию для примера:

1 происходит 4 раза (4 кратных), 2 - 2 раза (2 мультипликатора), 3 - 1 раз (3 мультипликатора), 4 - 1 раз (1 кратный)

Поэтому умножим 1 на 13, 2 на 13, 3 на 13, 4 на 13 (первые 4 кратные 1)

умножим 2 на 29, 4 на 29 (первые 2 кратные 2)

умножим 3 на 71 (сначала кратное 3)

умножим 4 на 1 (так как C[4] не существует)

Это дает чистый результат умножения 1 на 13, 2 на 13 * 29, 3 на 13 * 71, 4 на 13 * 29

Этот подход заканчивается тем, что \ $ O (N * log (N)) \ $, потому что для каждого N вы выполняете умножения N /i, что означает, что вы делаете в общей сложности:

N/1 + N/2 + N/3 + N/4 + ... N/N = N * (1/1 + 1/2 + 1/3 + ... + 1/N) = O(Nlog(N)),

, так как (1/1 + 1/2 + 1/3 + ...) является гармонических рядов и растет с \ $ O (log (N)) \ $

Вот соответствующий код, который дал результаты менее чем за 2 секунды, в основном из-за очень неэффективного ввода-вывода. Я изменил BigIntegers на Longs, так как BigIntegers очень SLOW в Java. Я также неоднократно использовал модульное умножение. Эти два предложения были подняты rofl, но я хотел повторить их повторение.

import java.io.*;
import java.util.*;

public class Solution {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       Long N = scanner.nextLong();
       Long M = scanner.nextLong();
       scanner.nextLine();

       ArrayList<Long> A = new ArrayList<Long>();
       ArrayList<Long> B = new ArrayList<Long>();
       ArrayList<Long> C = new ArrayList<Long>();

       A.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           A.add(new Long(string));
       }
       B.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           B.add(new Long(string));
       }
       C.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           C.add(new Long(string));
       }

       HashMap<Long, Long> counts = new HashMap<Long, Long>();

       for (int i = 1; i < M+1; i++) {
           if (counts.containsKey(B.get(i))) {
               counts.put(B.get(i), (counts.get(B.get(i)) * C.get(i)) % 1000000007L);
           }
           else {
               counts.put(B.get(i), C.get(i));
           }
       }

       for (Long i = 1L; i < N+1; i++) {
           for (Long j = 1L; j < (N / i) + 1L; j++) {
               if (counts.containsKey(i)) {
                   A.set((int)(i * j), (A.get((int)(i * j)) * counts.get(i)) % 1000000007L); 
               }
           }
       }

       System.out.print(A.get(1));
       for (int i = 2; i < A.size(); i++) {
           System.out.print(" " + A.get(i));
       }
    } 
}
ответил mleyfman 27 AM00000080000005331 2014, 08:39:53
15

В 1801 году парень по имени Карл Фридрих Гаусс изучил проблемы, в которых завершалась числовая строка, называемая модульной арифметикой.

В своих исследованиях он доказал, что:

$$     (a \ times b) \ \% \ n = [(a) \ \% \ n \ times (b) \ \% \ n] \ \% \ n $$

Кроме того, 1000000007 является простым числом, что означает, что есть другие преимущества ...

И это также меньше половины Integer.MAX_VALUE.

Наконец, два значения int, независимо от того, насколько они велики при умножении, никогда не будут больше, чем Long.MAX_VALUE

Объединяя все это, вы можете переписать свой код без математики BigInteger, например:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (j % B[i] == 0) {
            A[j] = (int)( ( (long) A[j] * C[i]) % 1000000007L);
        }
    }
}
System.out.println(Arrays.toString(A));

Итак, используя некоторую математику, вы можете полностью устранить проблему BigInteger и сохранить ее как long и int.

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

Обратите внимание, что для больших чисел BigInteger имеет сложность \ $ O (s) \ $, где s - величина числа при умножении. Чем больше число, тем медленнее продукт. Таким образом, ваша сложность для вашего текущего решения - \ $ O (nms) \ $, где n - размер массива A, m - размер массивов B и C, а s - средний размер используемых BigIntegers. Путем уменьшения проблемы до значений размера, мы уменьшаем временную сложность на полный порядок до просто \ $ O (nm) \ $.

Вероятнее всего, вы сможете решить математику в O (n) времени ... Мне просто нужно подумать о том, как реструктурировать if в циклах

ответил rolfl 26 PM00000050000003431 2014, 17:40:34
7

В исходном сообщении использовались массивы на основе 1. Если вы измените их на 0, вы должны проверить (j + 1)% B [i] == 0, а не j% B [i] == 0.

for (int j = 0; j < M; j++) {
    if ((j+1) % B[i] == 0) {
        ...
    }
}

И это можно переписать:

for (int j = B[i]-1; j < M; j+=B[i]) {
    ...
}

Он может быть быстрее зависит от того, насколько велики B [i].

ответил Florian F 26 PM00000050000005331 2014, 17:55:53
2

Другие ответы уже относятся к

  • с использованием модульной (long) целочисленной арифметики (rolfl)
  • ускорение внутреннего цикла путем прогнозирования результата if (Florian F)

Третье возможное ускорение состоит в объединении равных значений \ $ B \ $. Если одно и то же значение \ $ B_i \ $ встречается \ $ k \ $ раз, вы можете обрабатывать их все вместе с \ $ k - 1 + \ frac {M} {B} \ $ модульными умножениями вместо \ $ \ frac {kM } {B} \ $.

Используя эти три оптимизации, мой худший тестовый пример занял 0.19s, и я даже не использовал другую общую оптимизацию (для HackerRank и подобных соревнований) - а именно, чтобы мой ввод-вывод был быстрым даже для большого ввода .

ответил Hagen von Eitzen 26 PM000000110000003731 2014, 23:11:37

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132