Можно ли дополнительно оптимизировать этот код, чтобы я не получал превышение лимита времени или TLE на конкурирующем веб-сайте? - PullRequest
Новая
       28

Можно ли дополнительно оптимизировать этот код, чтобы я не получал превышение лимита времени или TLE на конкурирующем веб-сайте?

0 голосов
/ 02 августа 2020

Снимок вопроса

На конкурентном веб-сайте кодирования я столкнулся с этим вопросом. Я смог решить эту проблему для базовых c вариантов использования, используя приведенный ниже код. Однако предел времени превышен для больших входных данных, и я попытался уменьшить количество циклов, но все же затраченное время составляет около 2 секунд, однако ограничение составляет только 1 секунду. оптимизировать этот код? Например, можем ли мы удалить вложенные циклы? 

static void Main(string[] args)
    {
        string[] first = (Console.ReadLine()).Split(null);          //Sample input -  3 1 2 2 3
        int N = int.Parse(first[0]);
        int X = (int.Parse(first[1]) - 1);
        int Y = (int.Parse(first[2]) - 1);
        int Z = (int.Parse(first[3]) - 1);
        int T = (int.Parse(first[4]) - 1);
        string second = Console.ReadLine();                         // Sample input - 1 2 3
        List<int> list = new List<int>();

        //Converting string inputs to int
        list = second.Split().Select(str => int.Parse(str)).ToList();

        List<int> xorList = new List<int>();
        int xor = 0;
        int temp = 0;
        //Calculate the digits(using bitwise AND) of sub-matrix only, instead of entire matrix, and in the same loop, calculate bitwise XOR also.
        for (int i = X; i <= Z; i++)
        {
            for (int j = Y; j <= T; j++)
            {
                temp = list[i] & list[j];
                xor ^= temp;                    
            }
        }            
        Console.WriteLine(xor);            
    }

EDIT: Для больших входных данных размер матрицы может достигать 100000 на 100000. Также последовательность чисел может иметь целые числа размером до 1000000000.

Для таких целых чисел требуется 2 секунды.

1 Ответ

1 голос
/ 02 августа 2020

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

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

введите описание изображения здесь

Затем задача состоит в том, чтобы подсчитать количество пересечений и определить, четное ли это число (результат: ноль) или нечетное (результат: один).

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

* 1013 количество логических значений True в диапазоне X..Z и Y..T.

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

Возможно, вы предпочитаете более алгебраическое c объяснение , то способ увидеть это заключается в том, что мы используем тот факт, что AND распределяет по XOR для перезаписи a&d ^ a&e ^ a&f ^ b&d ^ b&e ^ b&f ^ c&d ^ c&e ^ c&f (пример 3x3) в (a ^ b ^ c) & (d ^ e ^ f).

В общем, 

horizontal = XOR of list[X .. Z]
vertical = XOR of list[Y .. T]
result = horizontal & vertical
...