FR_03_03 - Zbior liczb niepodzielnych

[rafal06]

Witam, czy mógłby mi ktoś podać jakiś podchwytliwy test do tego zadania? Ewentualnie, jakąś wskazówkę, gdzie poprawić kod, który wydaje mi się, że zwraca poprawne odpowiedzi, jednak dalej nie ma AC.
https://ideone.com/wE2Wwb

[narbej]

Program, nawet po znalezieniu i poprawieniu błedu będzie prawdopodobnie dużo za wolny [tle].
Takie dane:
4
2 2 3 4
2
1 10
10 20
powinny dać taki sam wynik jak w przykładzie w zadaniu, a nie dają.

[aididas]

Po zgłoszeniu mojego kodu dostaje "błędną odpowiedź" i nie mogę rozkminić dlaczego. Potrzebuje testu który obala ten algorytm. Oto kod (C++):

#include<cstdio>

int main()
{
    int n,x,q,a,b,i,l,j,*ile;
    bool *t;
    t=new bool[1000001];
    ile=new int[1000001];
    for(i=0;i<1000001;i++)
    {
        t[i]=false;
    }
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        for(j=x;j+x<1000001;j+=x)
        {
            t[j]=true;
        }
    }
    ile[0]=0;
    l=0;
    for(i=1;i<1000001;i++)
    {
        if(!t[i])
        {
            l++;
        }
        ile[i]=l;
    }
    scanf("%d",&q);
    while(q>0)
    {
        scanf("%d %d",&a,&b);
        l=ile[b]-ile[a];
        if(!t[a])
        {
            l++;
        }
        printf("%d\n",l);
        q--;
    }
}

[mariusz193]

twój program plus dane testowe

[aididas]

Ok, ten dość irytujący błąd naprawiony, a jeszcze pomyślałem o drobnym skróceniu jednej z pętli. Takie są efekty:

#include<cstdio>

int main()
{
    int n,x,q,a[10000],b[10000],i,l,j,*ile,amin=-1,bmax=-1;
    bool *t;
    t=new bool[1000001];
    ile=new int[1000001];
    for(i=0;i<1000001;i++)
    {
        t[i]=false;
    }
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        for(j=x;j<1000001;j+=x)
        {
            t[j]=true;
        }
    }
    scanf("%d",&q);
    for(i=0;i<q;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        if((amin==-1)||(amin>a[i]))
        {
            amin=a[i];
        }
        if((bmax==-1)||(bmax<b[i]))
        {
            bmax=b[i];
        }
    }
    l=0;
    for(i=amin;i<=bmax;i++)
    {
        if(!t[i])
        {
            l++;
        }
        ile[i]=l;
    }
    for(i=0;i<q;i++)
    {
        l=ile[b[i]]-ile[a[i]];
        if(!t[a[i]])
        {
            l++;
        }
        printf("%d\n",l);
    }
}

Ale jak się okazuje wszystko na nic, no bo przekroczono limit czasu. Czy ten kod da się jakoś ulepszyć, czy może chodzi tu o coś zupełnie innego?

[narbej]

Ten kod jest gorszy, a nawet powiedziałym dużo gorszy od pierwszego. Próbujesz tu optymalizować szukając minimum i maksimum, co może przynieść faktycznie jakąś minimalną poprawę, dla mikroskopijnych danych [ale nie koniecznie], ale TLE masz dla największych danych - zawierających test-zapytanie: 1 1000000, a tu taka poprawka nic nie wnosia wręcz przeciwnie.

Stary kod [oprócz błędu]:

1. tablice dynamiczne stosuje się, gdy nie zna się z góry rozmiaru tablicy.
2. Dostęp do tablic dynamicznych i do globalnych jest [zawsze?] wolniejszy niż do statycznych lokalnych.
3. przeskoki [czytanie i pisanie] między dwoma tablicami [lub w ramach jednej] przerywają ciągłość wczytywanego [z pamięci RAM do szybszej pamięci podręcznej procesora] strumienia danych i bardzo spowalniają program. Czy nie wystarczy więc tu tylko jedna tablica?
4. Spróbuj wyobrazić sobie [lub metoda: ołówek + kartka] co się dzieje dla danych:
   2 4 6 8 10 12 ......
5. Jak wyżej: 2 2 4 4 4 6 6 6 6 ...
6. Jak wyżej ale inne kombinacje 3 6 9 .... + ewentualnie pkt 3 i pkt 4
7. Jak wyżej 1 1 1 1 1 1 1 1 1 1 1 1 1 ..........+ ewentualnie pkt 3 + pkt 4 + pkt 5
8. Jak wyżej ale w odwrotnej kolejności - jednak do AC sortowanie jest zupełnie zbędne

Na pewno 1 z powyższych pkt powoduje u Ciebie TLE, ale może pozostałe też się trochę przyczyniają.

PS
tego nie rob się tak:

l=ile[b]-ile[a];
if(!t[a])
{
    l++;
}
printf("%d\n",l);

Tylko:
printf......ile[b] - ile[a-1] //gdy a > 0
printf......ile[b] /// dla a == 0 <-- w tym zadaniu nie ma takiego a

[aididas]

Rzeczywiście 1 z powyższych pkt powodował TLE. Trafnym okazał się 4. punkt. Trochę bałem się zagłębiać we właściwości multizbioru A, ale jak to się okazało - niepotrzebnie. Po poprawce z tą kwestią związanej udało się zaliczyć z czasem 0,02.

Dalej to posłuchałem jeszcze kilku kolejnych rad:
- nie robienie tylu przeskoków (pkt 3) - czas: 0.01
- ostatecznie dodanie sortowania (pkt 8) - czas: 0.00

Zadanie wykonałem. Dziękuje wam obu za pomoc.

//------------------------------------------------------------------------------

Zastanawia mnie jednak kwestia tablic statycznych a dynamicznych. Kiedy na starcie zadeklarowałem tablice o dużym rozmiarze:

int ile[1000001];
bool t[1000001];

no to już danych nie mogłem wpisać w trakcie pracy programu, bo się po prostu rozsypywał. Tak więc musiałem podejść tu dynamicznie:

int *ile;
bool *t;
ile=new int[1000001];
t=new bool[1000001];

Dobrze mówię, czy może jednak da się tu jakoś wcisnąć te tablice statycznie?

[mariusz193]

da się, ale jako globalne,
tablice globalne, oraz te tworzone jako new Typ[] zajmują miejsce w przestrzeni danych (czyli tyle, ile pozwala system operacyjny, czasami ograniczenie nakłada też autor zadania) , te tworzone lokalnie w procedurze zajmują miejsce na stosie - default wynosi 8 MB

[narbej]

Kiedy na starcie zadeklarowałem tablice o dużym rozmiarze:

Jesteś za bardzo zachłanny. Jedna tablica się zmieści na stosie [tablica lokalna] dwie już nie, a przecież jedna wystarczy.

[redysz]

Czy może mi ktoś podpowiedzieć jak to przyspieszyć?
link

Sens:

0. Tworzę tablicę miliona zer
1. Pobieram zbiór (w ten sposób unikam powtórzeń)
2. Sortuje go na vector (więcej liczb podzieli się przez mniejsze dzielniki niż przez większe więc łatwo sprawdzać od lewej do prawej)
3. Pobieram a i b
4. Sprawdzam wszystkie wartości z tablicy od a do b. Jeżeli jest 0, to sprawdzam czy się przez coś dzieli i ustawiam odpowiednio 1 - nie dzieli się, 2 - dzieli się. Jeżeli jest 1 to tylko inkrementuję ilość liczb w przedziale, jeżeli 2 to pomijam.
5. Wyświetlam ilość

Niestety przekraczam czas - czy to trzeba zrobić inacze? Na przykład jakimś drzewem przedziałowym?

[yula]

ja dla zapytań tylko przelatuje wcześniej przygotowaną tablicę, już nic nie licze

[redysz]

W sensie raz tworzysz tablicę (załóżmy podobną do mojej) true-falsów (czy innych 0-1) i jedziesz później po niej? Próbowałem tak zrobić i też miałem przekroczony limit czasu. Robiłaś coś jeszcze? Typu jeszcze szybsy I/O lub cokolwiek?

[mariusz193]

pomyśl nad czymś dużo prostszym
a w szczególności postaraj się zrozumie, co napisała yula

[yula]

Mam odpowiednio przetworzony pierwszy podany zbiór. I zrobione na cin.cout Więc o szybki IO nie ma mowy

[redysz]

Ok. Rozumiem, wydawało mi się, że i tego próbowałem, ale może po prostu coś zrobiłem zbyt dobrze i wyszło jak zwykle Spróbuję jutro.

[yula]

pomyśl co masz sprawdzić i co musisz mieć by zrobić to szybko

[redysz]

Tym razem udało mi się (chyba) tak właśnie to wykonać, jest o wiele szybciej, ale nadal przekraczam czas. Coś jeszcze może to przyspieszyć? Mam np. sprawdzać czy przypadkiem na wejściu nie otrzymuję kilku takich samych liczb w multizbiorze?

Edit: tak, to też trzeba było zrobić. Jest AC. Dzięki

PS. Mam ten sam czas co Ty. Ciekawe jak można to było zrobić by zmieścić się w 0.00 - 0.01. Czy ktoś może podesłać kod z takim rozwiązaniem na priv? Albo poinformować, że dalej to tylko chodzi o szybszy I/O?

[narbej]

Nie, tym razem nie chodzi o fast i/o. Wysyłam Ci na priv mój kod, który zrobiłem na scanf/printf, ale możliwe, że wystarczyło by cin/cout - to mój stary kod, z drobnymi oczyszczającymi poprawkami.

[redysz]

@tarpauwatratar też mi wysłał kod i też tym pomysłem, także już jestem ugruntowany, że tak jest szybciej. Chociaż swoim kodem zdołałem osiągnąć 0.04 więc już jestem zadowolny

[yula]

Ze mną też podzielcie sie szybszym kodem