abdi Temat założony przez niniejszego użytkownika |
zadanie z VI OIG » 2012-07-08 22:59:31 Czesc. Mam problem z wydajnością mojego kodu w tym zadaniu: http://main.edu.pl/pl/user.phtml?op=showtask&task=prz&con=OIG6Mam informacje ze program został wywłaszczony czyli przekroczono czas oczekiwania. Gdyby ktoś mógł dać mi jakaś wskazówkę jak lepiej go napisać to bardzo bym prosił o odpowiedz. #include<iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio( 0 );
int liczba_licznikow;
int liczba_operacji;
int wprowadzony_przycisk;
int max_wartosc = 0;
int licznik_operacji = 0;
cin >> liczba_licznikow >> liczba_operacji;
int tablica_licznikow[ liczba_licznikow + 1 ];
int l = 0;
while( l != liczba_licznikow + 1 )
{
tablica_licznikow[ l ] = 0;
l++;
}
tablica_licznikow[ l ] = 0;
while( liczba_operacji )
{
cin >> wprowadzony_przycisk;
if( wprowadzony_przycisk == liczba_licznikow + 1 )
{
int l = 0;
max_wartosc = tablica_licznikow[ 0 ];
while( liczba_licznikow != l )
{
l++;
if( tablica_licznikow[ l ] > max_wartosc )
{
max_wartosc = tablica_licznikow[ l ];
}
}
l = 0;
while( l != liczba_licznikow + 1 )
{
tablica_licznikow[ l ] = max_wartosc;
l++;
}
tablica_licznikow[ l ] = max_wartosc;
}
else
{
tablica_licznikow[ wprowadzony_przycisk ] ++;
}
liczba_operacji--;
}
licznik_operacji = 1;
while( licznik_operacji != liczba_licznikow + 1 )
{
cout << tablica_licznikow[ licznik_operacji ] << " ";
licznik_operacji++;
}
}
|
|
DejaVu |
» 2012-07-08 23:23:27 Zadania konkursowe nie są po to abyś pytał się jak je rozwiązać aby były szybkie, tylko żebyś pomyślał jak napisać je aby działały szybko. Pierwsze co się rzuca w oczy to fakt użycia std::cin (w konkursach używa się scanfa), a drugie to wyszukiwanie liniowe 'maxa'. Treści zadania nie czytałem. |
|
OSA_PL |
» 2012-07-08 23:28:42 Skompilowałem ten kod i u mnie wszystko działa ok. |
|
abdi Temat założony przez niniejszego użytkownika |
» 2012-07-09 01:21:47 Masz racje tej petli wogole nie powinno byc. troche wydajnosc sie zwiekszyla. Jest teraz 55/100 a bylo 50. dodalem zamiast petli takie cos else
{
tablica_licznikow[ wprowadzony_przycisk ] ++;
if( tablica_licznikow[ wprowadzony_przycisk ] > max )
{
max = tablica_licznikow[ wprowadzony_przycisk ];
}
}
hm troche musze jeszcze nad tym posiedziec ale i tak dzieki za odpowiedz. @OSA wiem, przecież napisałem ze nie chodzi mi o błąd tylko o szybkosc programu :) |
|
ison |
» 2012-07-09 02:31:35 możliwych wciśnięć przycisków masz 10^6, dla rozpatrzenia każdego wciśnięcia możesz mieć maksymalnie czas logarytmiczny, jeśli robisz cokolwiek liniowo, tzn wyszukujesz maxa albo aktualizujesz resztę przycisków to masz za słabą złożoność ;) zawsze zakładaj pesymistyczny przypadek i obliczaj sobie ilość operacji, max to ~10^8 tutaj pesymistycznie możesz mieć 10^6 wciśnięć ostatniego przycisku, czyli wykonasz 10^6 * 10^6 operacji | // ustawienie maxymalnej wartosci wszystkim licznika |
licznikom a nie liczniką |
|
xevuel |
» 2012-07-09 06:57:02 Oto jak ja rozwiązałem to zadanie wtedy na konkursie: #include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio( 0 );
int n = 0, m = 0;
cin >> n >> m;
int a = 0;
int * array = new int[ n ];
for( int i = 0; i < n; i++ )
{
array[ i ] = 0;
}
int max = 0;
for( int i = 0; i < m; i++ )
{
cin >> a;
if( a <= n )
{
array[ a - 1 ] ++;
if( array[ a - 1 ] > max )
max = array[ a - 1 ];
}
if( a == n + 1 )
{
for( int j = 0; j < n; j++ )
{
array[ j ] = max;
}
}
}
for( int i = 0; i < n; i++ )
{
if( i == n - 1 )
{
cout << array[ i ];
break;
}
cout << array[ i ] << " ";
}
return 0;
}
Punktów: 63/100. Recz jest o tyle ciekawa, że w dużej mierze czas wykonania programu zależy też od systemu - przykładowo, wrzuciłem do archiwum ten sam kod, na którym zdobyłem te 63 pkt. Efekt? Tym razem tylko 56. Przerobiłem go tak, aby używał printf()i scanf() - 55 pkt. Wszystkie odpowiedzi prawidłowe, tylko limit czasu. Tak jak widzisz... trzeba mieć też trochę szczęścia, żeby na konkursie trafić na dobry moment :) Szczerze mówiąc to był pierwszy program, który pisałem "na czas" w konsoli (tak to tylko WinAPI), co pewnie widać. Twój kod: int tablica_licznikow[ liczba_licznikow + 1 ]; Hmm? Dodatkowo uważam, że nazywanie zmiennych takimi nazwami, jakie były użyte w treści zadania jest lepsze od nazywania po swojemu :) Tak jeszcze dodam swoją opinię odnośnie systemu punktacji na OIG. Moim zdaniem, to już gorszego się chyba wymyślić nie dało. Gdybym miał oceniać ten system, w skali 0...10 dałbym 2. |
|
ison |
» 2012-07-09 23:35:30 | Recz jest o tyle ciekawa, że w dużej mierze czas wykonania programu zależy też od systemu - przykładowo, wrzuciłem do archiwum ten sam kod, na którym zdobyłem te 63 pkt. Efekt? Tym razem tylko 56. Przerobiłem go tak, aby używał printf()i scanf() - 55 pkt. Wszystkie odpowiedzi prawidłowe, tylko limit czasu. Tak jak widzisz... trzeba mieć też trochę szczęścia, żeby na konkursie trafić na dobry moment :) |
Nie, żeby dostać 100 punktów nie trzeba mieć ani trochę szczęścia. Twój algorytm to zwykły brute, jest to rozwiązanie złożonościowo za wolne i nie może dostać 100 punktów bez względu na to czy używasz printfów czy czegokolwiek innego, jest po prostu błędne. | Moim zdaniem, to już gorszego się chyba wymyślić nie dało. |
na szczęście nie Ty o tym decydujesz ;) | Limit czasu ustawiony na 1 s: Jeśli program wykona Ci się w czasie 0.99 s, to mimo, że przecież wyrobiłeś się w czasie, to i tak nie dostaniesz ani jednego punkta. |
i bardzo dobrze, czas w jakim wykonuje się Twój program zależy od złożoności, jeśli napiszesz poprawny algorytm to czasy będą się mieściły w dolnej granicy limitu | System oceniania na finale: Zadania były podzielone na tak jakby kategorie, czyli np. 100 pkt możliwych podzielonych na dwie kategorie. W każdej kategorii po co najmniej 5 testów. I albo zaliczyłeś wszystkie testy w czasie, albo dostawałeś 0 pkt. Co prawda potem to zmienili ze względu na... ekhem... małą liczbę osób powyżej 0 pkt ;), no ale ten kto to wymyślał, musiał być nieźle narąbany wtedy. |
system jest bardzo dobry, uwala wszystkie rozwiązania heurystyczne, punktacja względem złożoności tak czy siak była dopasowana tak że jeśli miałeś bruta kwadratowego to testy były ułożone tak abyś dostał 30 pkt, jeśli napisałeś poprawne rozwiązanie to dostawałeś 100 Do tego można jeszcze dodać brak możliwości po konkursie sprawdzenia danych, na których był testowany program, co uniemożliwia już "na sucho" analizę własnych błędów, oraz kilka innych niedociągnięć.
|
te dane są niepotrzebne, mówisz o finale? jeśli tak to dostałeś kartkę z omówieniem wszystkich zadań, sam je rozdawałem :D ocena swojego programu pod względem złożonościowym jest bardzo ważna pogódź się z tym, że rozwiązać zadanie pod względem poprawnych odpowiedzi nie jest trudno, sztuką jest zrobienie tak aby Twój program to liczył w pół sekundy a nie 100000 lat jeśli myślisz, że Twój algorytm nie przeszedł bo wykonywał się przez 1 sekundę zamiast 0.99 to się mylisz, jeśli program działa dłużej niż pewny limit to jest po prostu zabijany i dostajesz TLE, chcesz wiedzieć ile działał Twój algorytm? skompiluj sobie ten program i policz po jakim czasie się skończy #include <cstdio>
int main()
{
int costam = 0;
for( int i = 0; i < 1000000; ++i ) {
for( int j = 0; j < 1000000; ++j ) {
costam += i * j;
}
}
printf( "%d\n", costam );
}
(to całe dodawanie tylko po to aby kompilator nie zoptymalizował tego i nie wywalił forów) |
|
abdi Temat założony przez niniejszego użytkownika |
» 2012-07-10 02:46:50 nareszcie 100/100 :D
nie wiem czy pokazywac kod czy sami wolicie to zrobic.
0 OK 0.00s/1.00s 0/0
0b OK 0.01s/1.00s 0/0
0c OK 0.00s/1.00s 0/0
1 OK 0.00s/1.00s 7/7
2 OK 0.00s/1.00s 7/7
3 OK 0.00s/1.00s 7/7
4 OK 0.00s/1.00s 7/7
5 OK 0.00s/1.00s 7/7
6 OK 0.00s/1.00s 7/7
7 OK 0.01s/1.00s 7/7
8 OK 0.03s/1.00s 7/7
9 OK 0.06s/1.00s 7/7
10 OK 0.14s/1.50s 7/7
11 OK 0.21s/2.00s 7/7
12 OK 0.58s/6.00s 7/7
13 OK 0.60s/6.00s 8/8
14 OK 0.57s/6.00s 8/8
Racja pol sekundy.
Dzieki DejaVu i ison ze naprowadziliscie mnie na ten blad.
pozdr. |
|
| « 1 » 2 3 |