Imprimă pagina - [Concurs] UVa - IIUC Programming Contest

Titlul: [Concurs] UVa - IIUC Programming Contest
Scris de: Bogdan-Cristian Tataroiu din Septembrie 05, 2006, 08:59:06

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

Titlul: Raspuns: [Concurs] UVa - IIUC Programming Contest
Scris de: Paul-Dan Baltescu din Septembrie 09, 2006, 15:54:19

Foarte orginala problema G... :P :-'

Titlul: Raspuns: [Concurs] UVa - IIUC Programming Contest
Scris de: Savin Tiberiu din Septembrie 10, 2006, 09:27:55

Mie nu mi-a placut ca a durat foarte mult sa imi evalueze solutia. :x 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??

Titlul: Raspuns: [Concurs] UVa - IIUC Programming Contest
Scris de: Paul-Dan Baltescu din Septembrie 10, 2006, 09:51:41

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?

Titlul: Raspuns: [Concurs] UVa - IIUC Programming Contest
Scris de: Mircea Pasoi din Septembrie 10, 2006, 11:14:31

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;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Concursuri => Subiect creat de: Bogdan-Cristian Tataroiu din Septembrie 05, 2006, 08:59:06