[Concurs] UVa - IIUC Programming Contest

[•bogdan2412]

Sambata, 9 septembrie, la ora 11:00, va avea loc un concurs pe acm.uva.es. Mai multe detalii aici

[•pauldb]

Foarte orginala problema G...   

[•devilkind]

Mie nu mi-a placut ca a durat foarte mult sa imi evalueze solutia.    Am primit mail cu Program received dar nu l-am m-ai primit pe cel de la evaluare, asa ca intre timp am renuntat, am inchis calculatorul si am plecat. Si diseara cand am ajuns acasa am gasit mailurile in Inbox si luasem TLE. BTW: Tasku D mergea mai repede de n^2? Banuiesc ca da, ati putea sa imi ziceti si mie cum??

[•pauldb]

Puteai face N log N in felul urmator (am luat TLE): Sortai numerele. Pentru fiecare element distinct  x calculai x mod k.
[daca numarul era negativ, atunci ((x mod k)+k) mod k ]. Tineai un vector c[0..k-1] cu numarul de aparitii al fiecarui rest. 
Calculai sol=Cmb(c[0],2)+ c[1]*c[n-1]+c[2]*c[n-2]+...c[(n-1)/2]*c[n-(n-1)/2].
Daca k era par atunci se aduna Cmb(c[k div 2],2).
In final mai ai de tratat cazul perechilor egale, in O(n).

Am incercat sa rezolv problema si in O(n) cu hash-uri, dar tot TLE am luat. 

Domino, imi zici si mie te rog cum ai facut?

[•domino]

Solutia mea este asemanatoare cu cea ai explicat tu. Sortezi in N*lg N (am folosit sort)si apoi tineam un vector cnt[0...K-1] ca sa numar de cate ori apare fiecare rest. Daca numarul era pozitiv bagam A[ i ]%K , iar daca era negativ bagam (K-(-A[ i ]%K))%K. Daca aveam restul tmp la elementul curent, adunam cnt[K-tmp]. (si mai e cazul cu perechi formate din acelasi element). Am pus sursa mai jos (a rulat vreo 8s din 10):

Cod:

#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100005
#define MAX_K 512
#define FOR(i, a, b) for (i = (a); i < (b); i++)
#define abs(x) ((x) < 0 ? -(x) : (x))
#define ll long long

int T, N, K, cnt[MAX_K], A[MAX_N];

int main(void)
{
    int i, j, t, tmp;
    ll Res;

    scanf("%d", &T);
    for (t = 1; t <= T; t++)
    {
        scanf("%d %d", &N, &K);
        FOR (i, 0, N) scanf("%d", A+i);

        sort(A, A+N);
        memset(cnt, 0, sizeof(cnt));
        for (Res = 0, i = N-1; i >= 0; i = j)
        {
            for (j = i; j >= 0 && A[j] == A[i]; j--);
            tmp = A[i] >= 0 ? A[i]%K : (K-(-A[i]%K))%K;
            Res += cnt[!tmp ? 0 : K-tmp]; cnt[tmp]++;
            if (i-j <= 1) continue;
            tmp += tmp; while (tmp >= K) tmp -= K;
            if (!tmp) Res++;
        }

        printf("Case %d: %lld\n", t, Res);
    }
    return 0;
}