PKU 2380 - Sales Report

Autor da análise: dinak

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2380

Resumo

Dados N registros, resumi-los em uma tabela. A tarefa é bem simples, mas o problemas são as limitações de tempo e memória.

É um problema de time attack. De início já vou dizendo que só consegui passar com C/C++, sempre dava TLE com GCC/G++.

Solução

Não dá para criar a matriz tabela 10^8 * 10^8, dá 8,8 peta entradas.

Eu crio uma tabela de registros in[N][3] e armazeno os valores de entrada, aproveito para pegar o maior identificador de loja e de produto, smax e pmax. Crios os vetores sm[smax+1] e pm[pmax+1], eles sevirão para mapear a entrada nos índices da minha matriz. Inicializo eles com 0 e depois rodo a entrada marcando sm[ in[i][1] ] = 1 e pm[ in[i][0] ] = 1:

for(i=0; i<n; i++){
    pm[ in[i][0] ] = 1;
    sm[ in[i][1] ] = 1;
}

Eu preciso de vetores com os identificadores das lojas e produtos sem gaps e em ordem, são pv e sv:

pn = 0;
for(i=0; i<pmax; i++)
    if(pm[i] == 1)
        pv[pn++] = i;
 
sn = 0;
for(i=0; i<smax; i++)
    if(sm[i] == 1)
        sv[sn++] = i;

Depois os vetores de mapeamento sm e pm têm que ter o índice correto dos vetores com identificadores:

for(i=0; i<pn; i++)
    pm[ pv[i] ] = i;
 
for(i=0; i<sn; i++)
    sm[ sv[i] ] = i;

Agora eu posso criar a tabela com o tamanho sn * pn e a inicializo com 0.
Pronto, já posso resumir a entrada na minha tabela.

for(i=0; i<n; i++)
    m[ sm[ in[i][1] ] ][ pm[ in[i][0] ] ] += in[i][2];

Os vetores pv e sv vão servir tb para imprimir a tabela. O mapeamento economiza bastante tempo. O gargalo está no laço do pmax e smax. Tb uso memset para economizar tempo nas incializações. Não sei como diminuir mais o tempo. Fiz 1250MS. O melhor cara fez com 391MS e olha que foi com G++;

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema