Re[6]: Сумма элементов квадратной матрицы (школьная олимпиада) - Алгоритмы

Здравствуйте, 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 в конце.

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

Здравствуйте, 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

Здравствуйте, 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;
}

Здравствуйте, 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;
}

Здравствуйте, 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 хотите запускать код — не забудьте стэк до гигабайта увеличить ..

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

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

Вам дана (не обязательно симметричная) матрица 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 секунд).

Здравствуйте, 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 ( то уже нафиг с пляжа). Ассимптотика таже (куб), но позволяет срезать углы.

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

Вот это

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

вызывает сомнения... Поясни пожалуйста, откуда ты это взял.

Здравствуйте, 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  |

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

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

Это школьная олимпиада

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

Отдельное Спасибо за код!

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

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

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

(в однопотоке)

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

какое то — лютое говно мамонта у них — там ..

Код был написан на Pascal (http://pascalabc.net/en/)

Здравствуйте, 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).

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

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

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

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

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

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

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

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

Спасибо Всем, кто принимал участие в решение!!!

Здравствуйте, 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

топовые процики — дадут прироста в однопотоке максимум — в 3-4 раза ..

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

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

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

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

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

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

может n максимум 300 ?

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

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

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

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

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

Т.е. по условию задачи (по правилам построения матрицы) все значения в матрице — от 0 до 106 включительно.
Может это можно/нужно как-то использовать?

Здравствуйте, 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 на ней

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

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

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

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

Да, задача та же. Автор не я

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

xma>может n максимум 300 ?

Нет, n = 3000. 300 хорошо работает и на паскале. Но проходят только первые 2 теста из 10, остальные Time Limit.

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

Решения пока не знаю. Код на С я пытался запустить в онлайн компайлере (тут) (сам я не работаю с С),
но безуспешно, поэтому ориентируюсь на Ваши, коллеги, результаты.

Возникает также вопрос, зачем диагональные элементы должны быть нулевыми. Они дают оптимизацию, которую предложил vlp, или что-то большее...

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

D>Решения пока не знаю.

тут фишка в том чтобы по аналогии с аналогичными (уже разобранными) задачами — провести оптимизацию ..

с нуля — это на неслабое научное исследование тянет .. (ну уж точно не то что с ноля всколупнуть за полчаса на олимпиаде можно),

сомневаюсь что кто то может быстро раскинуть систематику сумм в уме, чтобы провести оптимизации — да ещё и "по быстренькому" ..

D>Возникает также вопрос, зачем диагональные элементы должны быть нулевыми. Они дают оптимизацию, которую предложил vlp, или что-то большее...

ну да, раз сказано — значит какая то фишка в этом ..

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

xma>тут фишка в том чтобы по аналогии с аналогичными (уже разобранными) задачами — провести оптимизацию ..

с нуля — это на неслабое научное исследование тянет .. (ну уж точно не то что с ноля всколупнуть за полчаса на олимпиаде можно),

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

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

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

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

там не сказано что MT юзать нельзя ..

навалить 8-16 потоков с транспонированной матрицей, и уложишься во время ..

к тому же, потоки входят — в стандартную библиотеку C/C++ ..

	Скрытый текст
	Multithreading in C++ https://www.geeksforgeeks.org/multithreading-in-cpp/ A Tutorial on Modern Multithreading and Concurrency in C++ https://www.educative.io/blog/modern-multithreading-and-concurrency-in-cpp

всё элементарно — синхронизировать нифига не надо ..

Здравствуйте, 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

Имеем, что если
i=A j=B k=C результат сравнения будет тот же и в случаях
i=B j=C k=A
i=C j=A k=B
ибо для сравнения будут браться теже самые элементы.
Если тройки чисел повторять бесконечно, то возможно 3 варианта:
A>B>C
A<B<C
Считаем для 2<i<n, 1<j<i, 0<k<j потом для 0<i<n-2, i<j<n-1, j<k<n
Результаты складываем и умножаем на 3.

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

D>>[/q]
B>Имеем, что если
B>i=A j=B k=C результат сравнения будет тот же и в случаях
B>i=B j=C k=A
B>i=C j=A k=B
B>ибо для сравнения будут браться теже самые элементы.
B>Если тройки чисел повторять бесконечно, то возможно 3 варианта:
A>>B>C
B>A<B<C
B>Считаем для 2<i<n, 1<j<i, 0<k<j потом для 0<i<n-2, i<j<n-1, j<k<n
B>Результаты складываем и умножаем на 3.

https://rsdn.org/forum/alg/7923687.1
Говорят, все равно слишком медленно (в одном потоке больше 7 секунд на максимальной матрице). Я проверял — мое решение работает на моем компа за 19 секунд (C#, c оптимизациями в виде транспонированных матриц).

Если это школьная олимпиада и решения на Паскале, всякие SIMD и распараллеливания отпадают. Загадочно...

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

vlp>Говорят, все равно слишком медленно (в одном потоке больше 7 секунд на максимальной матрице). Я проверял — мое решение работает на моем компа за 19 секунд (C#, c оптимизациями в виде транспонированных матриц).
Хм... Записать числа в отсортированный список и заняться комбинаторикой? Хм... Сомневаюсь, что это будет быстрее.

vlp>Если это школьная олимпиада и решения на Паскале, всякие SIMD и распараллеливания отпадают. Загадочно...
На олимпиадах, в которых участвует мой чилдрен, можно писать на чём угодно. Хоть на си, хоть на джаве, хоть на бейсике. Главное — уложиться в лимиты по памяти (- джава) и времени (- бейсик).

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

B>На олимпиадах, в которых участвует мой чилдрен, можно писать на чём угодно.

папка за чилдрена пытается выиграть олимпиаду ?

B>Хоть на си, хоть на джаве, хоть на бейсике. Главное — уложиться в лимиты по памяти (- джава) и времени (- бейсик).

тогда потоки наше всё ..

интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее

)

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

xma>папка за чилдрена пытается выиграть олимпиаду ?

Он заочными брезгует. Школьными тоже. Больше по хакатонам со студентами шляется. Да и помощник из меня ещё тот: не знаю ни одного языка, дающего исполняемые файлы.

xma>тогда потоки наше всё ..

А память 512 метров как это оно?

xma>интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее

)

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

B>Да и помощник из меня ещё тот: не знаю ни одного языка, дающего исполняемые файлы.

в каком смысле ?

B>А память 512 метров как это оно?

4 байта * 3000^2 элементов = 36 мбайт, + ещё стока же на транспонированную матрицу — итого 72 мбайта

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

xma>в каком смысле ?
Я знаю о существовании разных методов сортировки. Но пользуюсь ORDER BY. Ещё GROUP BY неявно сортирует, но без 100% гарантии.

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

xma>тогда потоки наше всё ..

Это вряд ли. Время обычно в олимпиадных задачах считается как суммарное, затраченное всеми тредами, а не как календарное от пуска до завершения работы. Так ещё можно было бы предложить TSR подвесить: пока проверяющая программа будет проверять результат, резидент будет его досчитывать

xma>интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее

)

Только никто Вам там не подлинкует ни эту Вашу opencl, ни даже банальную gmp для длинной арифметики, извольте всё ручками.

	От:	kov_serg
	Дата:	13.01.21 20:38
	Оценка:	+2

	От:	watchmaker
	Дата:	13.01.21 00:33
	Оценка:	18 (2)

	От:	vlp
	Дата:	13.01.21 01:13
	Оценка:	2 (1) +1

	От:	watchmaker
	Дата:	13.01.21 17:01
	Оценка:	6 (1)

	От:	kov_serg
	Дата:	12.01.21 23:42
	Оценка:	2 (1)

От:	denisko	http://sdeniskos.blogspot.com/
Дата:	12.01.21 08:40
Оценка:

	От:	Буравчик
	Дата:	13.01.21 18:19
	Оценка:

От:	biochemist	https://www.anekdot.ru/i/caricatures/normal/20/7/27/1595846503.jpg
Дата:	14.01.21 05:01
Оценка:

От:	cures	cures.narod.ru
Дата:	14.01.21 17:11
Оценка:

	От:	FireHose
	Дата:	15.01.21 22:00
	Оценка: