Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 12.01.21 01:41
Оценка:
Здравствуйте.

Следующая задача была предложена на школьной олимиаде.

Вам дана (не обязательно симметричная) матрица A размера n × n из неотрицательных целых чисел, при этом все её диагональные элементы равны 0.
Найдите значение суммы
n n n
∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]).
i=1 j=1 k=1

Ограничение : 2 < n <= 3000


Простейшее решение с помощью тройного цикла (сложность O(n^3)) приводит к Time Limit на больших n (> 7 секунд).
Re: Сумма элементов квадратной матрицы (школьная олимпиада)
От: denisko http://sdeniskos.blogspot.com/
Дата: 12.01.21 08:40
Оценка:
Здравствуйте, december22, Вы писали:

D>Здравствуйте.


D>Следующая задача была предложена на школьной олимиаде.


D>

D>Вам дана (не обязательно симметричная) матрица A размера n × n из неотрицательных целых чисел, при этом все её диагональные элементы равны 0.
D>Найдите значение суммы
D> n n n
D> ∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]).
D>i=1 j=1 k=1

D>Ограничение : 2 < n <= 3000


D>Простейшее решение с помощью тройного цикла (сложность O(n^3)) приводит к Time Limit на больших n (> 7 секунд).


∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]). = min(diag(A* A * A))
A = L + U + D (==0), L — нижне треугольная , U — верхне-треугольная, D — диагональная (равно 0)
1. A^3 = (L + U)*(L + U)*(L + U), ( c учетом L * L =0, U * U = 0) = (LUL + ULU)
2. (прим. Если матрица симметричная, то все еще проще)
3. Далее diag(A + B) = diag(A^T +B^T) = diag(A^T +B) = > следовательно рассмотрим только A = L*UL, A_ii = sum_{j < i} (L_j * (UL_ji). Причем если в момент подсчета j-того терма A_ii > min ( то уже нафиг с пляжа). Ассимптотика таже (куб), но позволяет срезать углы.
<Подпись удалена модератором>
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: kfmn Россия  
Дата: 12.01.21 19:11
Оценка:
Здравствуйте, denisko, Вы писали:

Вот это

D>∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]). = min(diag(A* A * A))


вызывает сомнения... Поясни пожалуйста, откуда ты это взял.
Re: Сумма элементов квадратной матрицы (школьная олимпиада)
От: kov_serg Россия  
Дата: 12.01.21 23:42
Оценка: 2 (1)
Здравствуйте, december22, Вы писали:

D>Здравствуйте.


D>Следующая задача была предложена на школьной олимиаде.


D>

D>Вам дана (не обязательно симметричная) матрица A размера n × n из неотрицательных целых чисел, при этом все её диагональные элементы равны 0.
D>Найдите значение суммы
D> n n n
D> ∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]).
D>i=1 j=1 k=1

D>Ограничение : 2 < n <= 3000


D>Простейшее решение с помощью тройного цикла (сложность O(n^3)) приводит к Time Limit на больших n (> 7 секунд).

Очень странно. Очевидно что лучшее решение в общем случае будет >n^2

S=sum( min(Aij,Ajk,Aki, ijk) ) = sum( Aij*Cij , ij)
Если мы откуда-то занаем Cij то получаем n^2
Да и n небольшие всего 3000. Так что можно просто попробовать сократить доступ к данным, ну и векторизовать и распараллеливать
Если никаких ограничений кроме Aij целые, Aij>0 и Aii=0 нет то вряд ли что либо радикальное можно сделать.
Если попытаться рассчитать Cij то получается такая же асимптотика n^3 как и в варианте просто с циклами.

https://ideone.com/SQhtaK

int op=0;
int sum0(int n,int* A) {
    int i,j,k,v,Aij,Ajk,Aki,s=0; op=0;
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            Aij=A[i*n+j];op++;
            for(k=0;k<n;k++) {
                Ajk=A[j*n+k]; Aki=A[k*n+i]; op+=2;
                v=Ajk<Aki?Ajk:Aki;
                v=Aij<v?Aij:v;
                s=s+v;
            }
        }
    }
    return s;
}
int sum1(int n,int* A) {
    int i,j,k,Cij,Aij,Ajk,Aki,s=0; op=0;
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) { if (i==j) continue;
            Aij=A[i*n+j]; op++; if (Aij<=0) continue;
            for(Cij=k=0;k<n;k++) {
                Ajk=A[j*n+k]; op++; if (Aij>Ajk) continue;
                Aki=A[k*n+i]; op++; if (Aij>Aki) continue;
                if (Aij<Ajk && Aij<Aki) Cij+=3;
                else if (Aij==Ajk && Aij<Aki) Cij+=2;
                else if (Aij<=Ajk && Aij==Aki) Cij++;
            }
            s+=Aij*Cij;
        }
    }
    return s;
}

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[]) {
    enum { n=10 };
    int i,j,v,A[n*n];
    srand(time(0));

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            v=rand()%1000;
            A[i*n+j]=i==j?0 : v;
        }
    }

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) printf("%4d",A[i*n+j]);
        printf("\n");
    }

    printf("sum0=%d",sum0(n,A));printf(" op=%d\n",op);
    printf("sum1=%d",sum1(n,A));printf(" op=%d\n",op);
    
    return 0;
}
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 13.01.21 00:28
Оценка:
Здравствуйте, denisko, Вы писали:

D>∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]). = min(diag(A* A * A))

D>A = L + U + D (==0), L — нижне треугольная , U — верхне-треугольная, D — диагональная (равно 0)
D>1. A^3 = (L + U)*(L + U)*(L + U), ( c учетом L * L =0, U * U = 0) = (LUL + ULU)
D>2. (прим. Если матрица симметричная, то все еще проще)
D>3. Далее diag(A + B) = diag(A^T +B^T) = diag(A^T +B) = > следовательно рассмотрим только A = L*UL, A_ii = sum_{j < i} (L_j * (UL_ji). Причем если в момент подсчета j-того терма A_ii > min ( то уже нафиг с пляжа). Ассимптотика таже (куб), но позволяет срезать углы.

Спасибо за предложенный алгоритм, но он даёт неверный результат.
Рассмотрим матрицу
     | 0  1  2 |     
A =  | 4  0  3 |
     | 5  6  0 |


Сумма для данной матрицы будет (1 + 2) * 3 = 9.

В предложенном алгоритме

     | 0  0  0 |        | 0  1  2 |         | 14 12 0 |          | 0   0   0 |         | 0  0  0 |          | 0  14  64|               | 0   14  64 |
L =  | 4  0  0 |   U =  | 0  0  3 |   UL =  | 15 18 0 |   LUL =  | 56  48  0 |   LU =  | 0  4  8 |   ULU =  | 0  15  84|   LUL + ULU = | 56  63  84 |
     | 5  6  0 |        | 0  0  0 |         | 0  0  0 |          | 160 168 0 |         | 0  5  28|          | 0  0   0 |               | 160 168 0  |
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиад
От: watchmaker  
Дата: 13.01.21 00:33
Оценка: 18 (2)
Здравствуйте, kov_serg, Вы писали:

_>           Ajk=A[j*n+k]; op++; if (Aij>Ajk) continue;

Это, конечно, треш

В первом варианте в op считается число доступов, и в sum0 оно получается больше чем в sum1. Хорошо.
Но время работы такого кода будет описываться в первую очередь не той частью, что записана в строке слева, а той, что находится справа. Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.



_>Так что можно просто попробовать сократить доступ к данным


Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно


Хотя, конечно, можно заметить, что все слагаемые входят в сумму тройками, которые отличаются только циклической перестановкой, и замена for(j=0;j<n;j++) на for(j=i+1;j<n;j++) (и для k) позволит выкинуть лишнее вычисления, если просто домножить сумму на 3 в конце.


Разумеется, понятно, что средненькие реализации хороших алгоритмов обычно дают больше выигрыша, чем вылизанные реализации плохих алгоритмов. Но тут просто интересный пример получился, что буквально заменой нескольких символов можно существенно улучшить время работы даже тупого алгоритма.
Отредактировано 13.01.2021 0:48 watchmaker . Предыдущая версия .
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 13.01.21 00:43
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Да и n небольшие всего 3000. Так что можно просто попробовать сократить доступ к данным, ну и векторизовать и распараллеливать


Это школьная олимпиада и, как я понимаю, лучшей производительности тут нужно добиваться за счет алгоритмов, а не этих программистских штучек
("векторизовать и распараллеливать")

Отдельное Спасибо за код!
Re: Сумма элементов квадратной матрицы (школьная олимпиада)
От: vlp  
Дата: 13.01.21 01:13
Оценка: 2 (1) +1
Здравствуйте, december22, Вы писали:

Единственное, что в голову приходит — это трехкратное ускорение наивного алгоритма.

пусть m(i,j,k) = min(a[i,j], a[j,k], a[k,i])

тогда очевидно что m(i,j,k) = m(k,j,i) = m(j,k,i)

в таком случае можно вычислить оригинальную сумму как 

  n    n      n
3*∑    ∑      ∑ min(A[i,j],A[j,k],A[k,i])
  i=1 j=i+1 k=j+1
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад
От: xma  
Дата: 13.01.21 01:19
Оценка: 2 (1)
Здравствуйте, watchmaker, Вы писали:

W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.

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

а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..

при n = 1000, sum1 более чем на четверть быстрее sum0

  Скрытый текст
int op = 0;

int sum0(int n, int* A) {
    int s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int Aij = A[i * n + j]; //op++;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k]; 
                int Aki = A[k * n + i]; //op += 2;
                int v = Ajk < Aki ? Ajk : Aki;
                v = Aij < v ? Aij : v;
                s += v;
            }
        }
    }
    return s;
}

int sum1(int n, int* A) {
    int  s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int Aij = A[i * n + j]; //op++; 
            if (Aij <= 0) continue;
            int Cij = 0;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k]; //op++; 
                if (Aij > Ajk) continue;
                int Aki = A[k * n + i]; //op++; 
                if (Aij > Aki) continue;
                if (Aij < Ajk && Aij < Aki) Cij += 3;
                else if (Aij == Ajk && Aij < Aki) Cij += 2;
                else if (Aij <= Ajk && Aij == Aki) Cij++;
            }
            s += Aij * Cij;
        }
    }
    return s;
}

int sum0_v2(int n, int* A, int *At) {
    int s = 0; //op = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int Aij = A[i * n + j]; //op++;
            for (int k = 0; k < n; k++) {
                int Ajk = A[j * n + k];
                //int Aki = A[k * n + i]; 
                int Aki = At[k + n * i];
                //op += 2;
                int v = Ajk < Aki ? Ajk : Aki;
                v = Aij < v ? Aij : v;
                s += v;
            }
        }
    }
    return s;
}

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#include <chrono>
#include <iostream>

int main(int argc, char const* argv[]) {
    enum { n = 1000 };
    int A[n * n];
    int At[n * n];
    srand(time(0));

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            int v = rand() % 1000;
            A[i * n + j] = i == j ? 0 : v;
        }
    }

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            At[j * n + i] = A[i * n + j];
        }
    }

    //for (i = 0;i < n;i++) {
    //    for (j = 0;j < n;j++) printf("%4d", A[i * n + j]);
    //    printf("\n");
    //}

    //printf("sum0=%d", sum0(n, A));printf(" op=%d\n", op);
    //printf("sum1=%d", sum1(n, A));printf(" op=%d\n", op);

    auto start = std::chrono::high_resolution_clock::now();
    int sum = sum0(n, A);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    std::cout << "sum0("<< n << ", A) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";

    start = std::chrono::high_resolution_clock::now();
    sum = sum0_v2(n, A, At);
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "sum0_v2(" << n << ", A, At) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";

    ///*
    start = std::chrono::high_resolution_clock::now();
    sum = sum1(n, A);
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "sum1(" << n << ", A) = " << sum << " , Time " << (diff.count() * 1000.0f) << " ms\n";
    //*/

    getchar();

    return 0;
}


W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.

W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно

да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицей) в 12 раз над sum0, (код выше) ..

при n=3000, sum0 — не дождался

P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..
Отредактировано 13.01.2021 2:08 xma . Предыдущая версия . Еще …
Отредактировано 13.01.2021 2:06 xma . Предыдущая версия .
Отредактировано 13.01.2021 1:52 xma . Предыдущая версия .
Отредактировано 13.01.2021 1:51 xma . Предыдущая версия .
Отредактировано 13.01.2021 1:50 xma . Предыдущая версия .
Re[4]: Сумма элементов квадратной матрицы (школьная олимпиад
От: december22 СССР  
Дата: 13.01.21 01:34
Оценка:
Здравствуйте, xma, Вы писали:

xma>а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..


xma>(sum0 на проце 10 летней давности 6 секунд), думаю что на 5900X — может и в 1.5-2 секунды уложиться .. (в однопотоке)


xma>так что пусть обновят компы — на олимпиаде, какое то — лютое говно мамонта у них — там ..



Код был написан на Pascal (http://pascalabc.net/en/)
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 13.01.21 01:38
Оценка:
Здравствуйте, vlp, Вы писали:

vlp>Здравствуйте, december22, Вы писали:


vlp>Единственное, что в голову приходит — это трехкратное ускорение наивного алгоритма.


vlp>
vlp>пусть m(i,j,k) = min(a[i,j], a[j,k], a[k,i])

vlp>тогда очевидно что m(i,j,k) = m(k,j,i) = m(j,k,i)

vlp>в таком случае можно вычислить оригинальную сумму как 

vlp>  n    n      n
vlp>3*∑    ∑      ∑ min(A[i,j],A[j,k],A[k,i])
vlp>  i=1 j=i+1 k=j+1


vlp>


Да, до этого тоже догадались, но и этот алгоритм выдаёт Time Limit (проходят те же тесты, что и в наивном алгоритме, первые 2 из 10).
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: vlp  
Дата: 13.01.21 01:48
Оценка:
Здравствуйте, december22, Вы писали:

D>Да, до этого тоже догадались, но и этот алгоритм выдаёт Time Limit (проходят те же тесты, что и в наивном алгоритме, первые 2 из 10).

а есть какие-то детали того, на чем код тестируется и какие ограничения по времени?
(ну и реализация этого алгоритма может сильно плавать по скорости в зависимости от того, как ходить по матрице)
Re[4]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 13.01.21 02:04
Оценка:
Здравствуйте, vlp, Вы писали:

vlp>а есть какие-то детали того, на чем код тестируется и какие ограничения по времени?

vlp>(ну и реализация этого алгоритма может сильно плавать по скорости в зависимости от того, как ходить по матрице)

Ограничение по времени 7 секунд.

Код был написан на Pascal (http://pascalabc.net/en/) (и тестируется видимо там же),
но была возможность выбрать и С и другие языки.

Я так понимаю, что код kov_serg с оптимизацией watchmaker даёт необходимый результат (<7s) для n = 3000.

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

Спасибо Всем, кто принимал участие в решение!!!
Re[5]: Сумма элементов квадратной матрицы (школьная олимпиад
От: xma  
Дата: 13.01.21 02:23
Оценка:
Здравствуйте, december22, Вы писали:

D>Я так понимаю, что код kov_serg с оптимизацией watchmaker даёт необходимый результат (<7s) для n = 3000.


не даёт .. при n = 1000, 8.8 секунд (sum1),

при n = 3000, sum0_v2 (с дополнительной транспонированной матрицей At) = 33.8 секунды, (sum0 и sum1 — не дождался)

код тут,
https://rsdn.org/forum/alg/7923689?tree=tree
Автор: xma
Дата: 13.01.21


топовые процики — дадут прироста в однопотоке максимум — в 3-4 раза ..
Отредактировано 13.01.2021 2:24 xma . Предыдущая версия .
Re[5]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: xma  
Дата: 13.01.21 15:57
Оценка:
Здравствуйте, december22, Вы писали:

D>Ограничение по времени 7 секунд.


D>Я так понимаю, что код kov_serg с оптимизацией watchmaker даёт необходимый результат (<7s) для n = 3000.


так каково решение то ?

D>Если нет более светлых алгоритмических идей, то вопрос можно считать закрытым.


прокомментируйте что нить на тему комментария ниже,
https://rsdn.org/forum/alg/7923699?tree=tree
Автор: xma
Дата: 13.01.21


может n максимум 300 ?
Re[6]: Сумма элементов квадратной матрицы (школьная олимпиад
От: watchmaker  
Дата: 13.01.21 17:01
Оценка: 6 (1)
Здравствуйте, xma, Вы писали:

xma>при n = 3000, sum0_v2 (с дополнительной транспонированной матрицей At) = 33.8 секунды,


Может вы в компиляторе оптимизацию кода случайно выключили? Или железо совсем древнее?
clang5 под процессор почти десятилетней давности (i5-2400) перебирает варианты за 3.5сек, если цикл чуть размотать, то чуть меньше 3-х сек.
Хотя видно, что тут запас по времени всего в пару раз остаётся, и можно выйти за ограничение по времени, если взять процессор ещё старее, компилятор похуже и неправильно его настроить.

  Скрытый текст
#include <time.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>

#include <algorithm>
#include <chrono>
#include <vector>
#include <string>


template <class T>
static T Min(const T& a, const T& b, const T& c) {
    return std::min(a, std::min(b, c));
}


int naive(const int* m, int n) {
    auto a = [=](int r, int c) { return m[r * n + c]; };

    int s = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                int v0 = a(i, j);
                int v1 = a(j, k);
                int v2 = a(k, i);

                int v = Min(v0, v1, v2);

                s += v;

            }
        }
    }
    return s;
}

std::vector<int> Transpose(const int* m, int n) {
    std::vector<int> mt(n * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            mt[i + n * j] = m[i * n + j];
        }
    }
    return mt;
}


int solve1(const int* m, const int* mt, int n) {
    auto a = [=](int r, int c) { return m[r * n + c]; };
    auto at = [=](int r, int c) { return mt[r + n * c]; };

    int s = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int v0 = a(i, j);
            for (int k = i + 1; k < n; ++k) {
                int v1 = a(j, k);
                int v2 = at(k, i);

                int v = Min(v0, v1, v2);

                s += v;

            }
        }
    }
    return s * 3;
}


int solve3(const int* m, const int* mt, int n) {
    auto a = [=](int r, int c) -> const int& { return m[r * n + c]; };
    auto at = [=](int r, int c) { return mt[r + n * c]; };

    constexpr int bs = 4;

    int s = 0;
    for (int i = 0; i < n; ++i) {
        int j;
        for (j = i + 1; j + (bs - 1) < n; j += bs) {
            const int* v00 = &a(i, j + 0);

            for (int k = i + 1; k < n; ++k) {
                int z2 = at(k, i);
                for (int q = 0; q < bs; ++q) {
                    int u1 = a(j + q, k);
                    int x0 = Min(v00[q], u1, z2);
                    s += x0;
                }
            }
        }
        for (; j < n; ++j) {
            int v0 = a(i, j);
            for (int k = i + 1; k < n; ++k) {
                int v1 = a(j, k);
                int v2 = at(k, i);

                int v = Min(v0, v1, v2);

                s += v;
            }
        }
    }
    return s * 3;
}

std::vector<int> Gen(int n) {
    std::vector<int> m(n * n);
    auto ap = [&](int r, int c) { return &(m[r * n + c]); };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                *ap(i, j) = (unsigned)rand() % 1000;
            }
        }
    }
    return m;

}

class Timer {
public:
    Timer(const std::string& name)
        : Name(name)
    {
    }

    ~Timer() {
        std::chrono::time_point<std::chrono::high_resolution_clock> end  = std::chrono::high_resolution_clock::now();
        auto diff = end - start;
        std::cout << Name << "\t:\t" << std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() << "ms" << std::endl;
    }

private:
    std::string Name;
    const std::chrono::time_point<std::chrono::high_resolution_clock> start = std::chrono::high_resolution_clock::now();
};


int main(int argc, char* argv[]) {
    srand(time(0));
    int n = 9;
    if (argc >= 2) {
        if (1 != sscanf(argv[1], "%d", &n)) {
            return 2;
        }
    }

    std::vector<int> m = Gen(n);

    if (0)
    {
        Timer l("naive");
        const std::vector<int> mt = Transpose(m.data(), n);
        std::cout << "naive: " << naive(m.data(), n) << std::endl;
    }

    if (0)
    {
        Timer l("solve3");
        const std::vector<int> mt = Transpose(m.data(), n);
        std::cout << "solve3: " << solve3(m.data(), mt.data(), n) << std::endl;
    }

    if (1)
    {
        Timer l("solve1");
        const std::vector<int> mt = Transpose(m.data(), n);
        std::cout << "solve1: " << solve1(m.data(), mt.data(), n) << std::endl;
    }

    return 0;
}
Re: Сумма элементов квадратной матрицы (школьная олимпиада)
От: Буравчик Россия  
Дата: 13.01.21 18:19
Оценка:
Здравствуйте, december22, Вы писали:

D>Следующая задача была предложена на школьной олимиаде.


Предположу, что это та же самая задача.

https://www.cyberforum.ru/cpp-beginners/thread2766491.html

Все решения жюри работают для любых матриц, недиагональные элементы которых — целые неотрицательные числа от 0 до 107 − 1 включительно, а диагональные элементы равны 0.


Т.е. по условию задачи (по правилам построения матрицы) все значения в матрице — от 0 до 106 включительно.
Может это можно/нужно как-то использовать?
Best regards, Буравчик
Re[7]: Сумма элементов квадратной матрицы (школьная олимпиад
От: xma  
Дата: 13.01.21 19:32
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Может вы в компиляторе оптимизацию кода случайно выключили?


ничего не выключал — пустой проект в MVS -> release x64, запускаю — напрямую, без отладчика

W>Или железо совсем древнее?


да не особо древнее i5-2400 почти одногодки, топчег в своё время

W>clang5 под процессор почти десятилетней давности (i5-2400) перебирает варианты за 3.5сек,


на Phenom II 965 BE при n = 2000, уже больше 10 секунд .. (проц максимум на 25-30% медленнее i5-2400)

W> int n = 9;


а чё так скромненько то ? ты задай n = 3000;

W> if (1 != sscanf(argv[1], "%d", &n)) {


последнюю MVS — я так понимаю что ты не юзаешь ? ибо sscanf теперь depricated на ней
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: kov_serg Россия  
Дата: 13.01.21 20:38
Оценка: +2 :)
Здравствуйте, Буравчик, Вы писали:

Б>Предположу, что это та же самая задача.


Б>https://www.cyberforum.ru/cpp-beginners/thread2766491.html


Б>

Б>Все решения жюри работают для любых матриц, недиагональные элементы которых — целые неотрицательные числа от 0 до 107 − 1 включительно, а диагональные элементы равны 0.


Б>Т.е. по условию задачи (по правилам построения матрицы) все значения в матрице — от 0 до 106 включительно.

Б>Может это можно/нужно как-то использовать?
Гы гы гы. Это не 107 а 10^7
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
От: december22 СССР  
Дата: 13.01.21 21:07
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, december22, Вы писали:


D>>Следующая задача была предложена на школьной олимиаде.


Б>Предположу, что это та же самая задача.


Да, задача та же. Автор не я
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.