Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Program wywłaszczony - co to znaczy?

Ostatnio zmodyfikowano 2012-04-21 12:58
Autor Wiadomość
Dawidsoni
Temat założony przez niniejszego użytkownika
Program wywłaszczony - co to znaczy?
» 2012-04-20 20:21:18
Witam! Robię sobie zadania ze strony main.edu.pl. Zrobiłem zadanie "Taśma" (treść zadania: ZADANIE TAŚMA) i po sprawdzeniu jego przy niektórych testach otrzymałem komunikat: "Program wywłaszczony". Niektórzy piszą, że program nie mieści się w przedziale czasowym i dlatego jest taki komunikat. Jednak to by było bardzo dziwne, bo na 40% przykładów, które mi uznaje mam czas z przedziału od 0.00 s. do 0.03 s. , a maksymalny czas wynosi 4.00. O to mój kod programu:

C/C++
#include<stdio.h>

int wynik( int * wsk, int ile ) {
    int odleglosc = 0;
    for( int i = 0; i < ile; i++ ) {
       
        for( int ii = ile - 1; ii > i; ii-- ) {
            if( wsk[ i ] != wsk[ ii ] && ii - i > odleglosc ) {
                odleglosc = ii - i;
                break;
            }
            if( odleglosc > ii - i )
                 break;
           
        }
        if( ile - i < odleglosc )
             break;
       
    }
   
    return odleglosc;
}


int main() {
    int ile, * odleglosc, * wczytaj, n;
    scanf( "%d", & ile );
    odleglosc = new int[ ile ];
   
    for( int i = 0; i < ile; i++ ) {
        scanf( "%d", & n );
        wczytaj = new int[ n ];
        for( int ii = 0; ii < n; ii++ ) {
            scanf( "%d", & wczytaj[ ii ] );
        }
        odleglosc[ i ] = wynik( wczytaj, n );
        delete[] wczytaj;
       
    }
    for( int i = 0; i < ile; i++ ) {
        if( odleglosc[ i ] == 0 )
             printf( "BRAK\n" );
        else {
            printf( "%d", odleglosc[ i ] );
            printf( "\n" );
        }
    }
    return 0;
}

Proszę o wskazanie przyczyny nie działania tego programu w niektórych testach i rozwiązanie go.
P-54912
DejaVu
» 2012-04-20 21:52:31
Bo część zadań ma mały zbiór testowy, a część duży. Małe zadania służą do testowania poprawności rozwiązania, duże do wydajności. Twój algorytm najwyraźniej daje poprawne rozwiązania, jednak jego szybkość działania pozostawia wiele do życzenia dla dużych zbiorów danych.
P-54920
Admixior
» 2012-04-20 21:52:32
Sorry przeczytałem na necie i wiem co to jest wywłaszeczenie xD

Za szybko odpisałem

//PS do admina: Czemu tamten jeden temat co się tyle opisałem został usunięty ???
P-54921
akwes
» 2012-04-20 22:08:37
@Admixior,

Bo tematy odnośnie łamania zabezpieczeń należy kierować na inne fora. Tutaj dla takich tematów nie ma trafy ulgowej. Nawet nie chodzi o prawo, ale uczymy pasji programowania, a nie pasji łamania. Od tego są inne fora. Jesteśmy po jasnej stronie mocy.

//DejaVu, sorry za offtop.

@Dawidsoni
wczytaj = new int[ n ];
Zadanie koniecznie musi mieć dynamiczną alokacje? Dynamiczna alokacja jest wolna, dużo wolniejsza od zmiennych przechowywanych na stosie. Może masz ograniczenie rozmiaru zbioru?

Może warto sprawić jak program zareaguje na zmianę funkcji modyfikatorem inline.
P-54922
Dawidsoni
Temat założony przez niniejszego użytkownika
» 2012-04-20 22:58:48
Dynamiczna alokacja nie jest konieczna, jednak ja jestem trochę przyzwyczajony, że w własnych, większych programach używam w 90% jej, a nie tablicy, bo nie zawsze wiem, ile co ma mieć elementów. Więc dynamiczna alokacja w większych projektach sprawdza się 100 razy lepiej. Jednak to zadania konkursowe i mam 32 mb limitu, więc może rzeczywiście zrobię na początku: int wczytaj[10000000]. Jutro to poprawię i powiem wam, czy polepszyło to coś. Funkcje na inline też zmienię.
P-54926
ison
» 2012-04-20 23:33:11
Zadanie koniecznie musi mieć dynamiczną alokacje? Dynamiczna alokacja jest wolna, dużo wolniejsza od zmiennych przechowywanych na stosie.
to nie ma znaczenia, różnica jest nieznacząca

Może warto sprawić jak program zareaguje na zmianę funkcji modyfikatorem inline.
Prawdopodobnie nie zareaguje w ogóle, kompilator i tak najprawdopodobniej to zignoruje albo uzna za lekką sugestię. Kompilator sam wie gdzie najlepiej wstawić inline a gdzie nie ;)

problem leży w złożoności
C/C++
for( int i = 0; i < ile; i++ ) {
   
    for( int ii = ile - 1; ii > i; ii-- ) {
to jest złożoność kwadratowa, to że w drugim forze zamiast lecieć do 0 lecisz do i powoduje tylko, że z n^2 robi ci się (n^2)/2 co nadal jest bardzo wolne

napisałeś brute'a i dostałeś 40% ;) na max testach program poległ
P-54928
akwes
» 2012-04-20 23:42:49
@ison,

nie wgłębiałem się zbytnio w kod, ale co do optymalizacji to widywałem że programy z printf nie przechodziły bo wymagane były funkcje pokroju fread/fwrite. Założyłem (błędnie) że to jedno z tych zadań, a autor już miał optymalną metodę.
P-54929
Dawidsoni
Temat założony przez niniejszego użytkownika
» 2012-04-21 12:36:14
A ma ktoś pomysł na optymalizację tego kodu?
P-54946
« 1 » 2
  Strona 1 z 2 Następna strona