Problema SANDUBA (SPOJ Brasil)

Lucas Maciel, Outubro de 2012

O problema a ser resolvido neste tutorial é o Sanduíche-íche-íche de Atum. É um problema ADHOC simples.

Resumo do enunciado

Dada uma matriz triangular superior M, seus elementos tem o valor de M[i, j] = Ai*Aj, sendo A uma sequencia dada de 10⁵ elementos. Calcule o somatório de todos os elementos da matriz M. Observação: os resultados devem ser impressos módulo 1300031.

Leitura da Entrada

Lemos a entrada de maneira simples, primeiro lendo o número de casos de teste. Podemos definir o vetor A já com o tamanho total no inicio da função principal e depois ler os dados até o n do caso teste. Exemplo:

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 100000 //10^5 elementos será o tamanho máximo do vetor
#define MOD 1300031

int main () {
    int A[MAX];  //não será necessário alocar a memória dinâmicamente
    int t, n;
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &A[i]);
    }
    return 0;
}

Obs: Note que até aqui apenas lemos a entrada, não resolvemos o problema.

Primeira Solução: Trivial em O(n² )

O problema pode ser reescrito dessa forma: Seja A o conjunto de elementos de tamanho n, é definido o somatório S = Ai*Aj para todo 1 <= i <= n e i <= j <= n. Um exemplo: Seja A = {A1, A2, A3}. Então teremos S = A1*A1 + A1*A2 + A1*A3 + A2*A2 + A2*A3 + A3*A3. Para calcular este tipo de operação usando algoritmos basta apenas aplicar a definição do somatório. Você pode verificar a validade desta solução com os casos de exemplo no enunciado da questão. Perceba que esta solução tem complexidade O(n² ). Lembre-se de efetuar a operação de módulo a cada cálculo.

Segunda Solução: Simples em O(n)

Devido a complexidade da primeira solução, é provável que exceda o tempo limite do problema, resultando em TLE (Tempo Limite Excedido). Para isso, vamos fazer algumas simplificações, usando o exemplo acima: Sabemos que S = A1*A1 + A1*A2 + A1*A3 + A2*A2 + A2*A3 + A3*A3 para A = {A1, A2, A3}. Se fizermos distribuição em S, temos: S = A1*(A1 + A2 + A3) + A2*(A2 + A3) + A3*(A3). Consideremos P1 = A1 + A2 + A3. P2 = P1 – A1 e P3 = P2 – A2. Logo nosso S = A1*P1 + A2*P2 + A3*P3. Perceba que a cada iteração, podemos calcular os valores de P e multiplica-los pelos elementos de A, tendo um custo O(n). A regra acima pode ser extendida para tamanhos arbitrários de A, ou seja, P(i+1) = Pi – Ai e o somatório S = Pi*Ai para 1 <= i <= n.

Detalhes de implementação

É altamente recomendado NÃO olhar o código antes de tentar a sua própria implementação.

Podemos calcular o P1 enquanto lemos a entrada de A, além de que não precisamos implementar um vetor para P. Os valores devem ser representados em um long long (8 bytes) e o módulo deve ser retirado a cada operação a fim de evitar overflow.

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 100000
#define MOD 1300031

typedef long long llong; //apenas para evitar de escrever 'long long' a cada declaração

llong mod(llong x){
    return ((x%MOD)+MOD)%MOD;  //evita módulos negativos
}

int main(){
    llong A[MAX];
    int t, n;
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        llong P = 0, S = 0;
        for (int i = 0; i < n; ++i){
            scanf("%lld", &A[i]);
            P += A[i];
        }
        for (int i = 0; i < n; ++i){
            S = mod(S+mod(mod(P)*A[i]));
            P -= A[i];
        }
        printf("%lld\n", S);
    }
    return 0;
}