Apr 2017
1 / 16
Apr 2017
Apr 2017
tomosatomos
Apr '17

Czy mogę prosić o jakieś podchwytliwe testy? Nie wiedzieć czemu mam złą odpowiedź przy moim zgłoszeniu 19203109

mariusz193
Apr '17

a po co podchwytliwe testy, i co może być podchwytliwego w liczbach z zakresu 1..1000000 ?

może po prostu sprawdź wyniki dla kilku liczb bliskich 1 i kilku bliskich maksymalnej wartości

loginus
Apr '17

Stawiam na :
1. Masz zły algorytm .
2. Użyłeś za małego typu zmiennej liczbowej i wynik przekracza maksymalną wartość .

kapi3993
Apr '17

Mam podobny problem; używam C++, gdy użyję zmiennej o mniejszej wartości maksymalnej odpowiedź jest błędna (co jest logiczne) lecz gdy użyję zmiennej o większej wartości maksymalnej (w moim wypadku long long) test wypada negatywnie ze względu na przekroczenie limitu czasu. Ograniczyłem wszystkie znaki do minimum, sprawdzałem różne pętle, wszystko na nic, limit czasu i tak przekroczony. Czy ma ktoś jakieś wskazówki lub propozycje?

loginus
Apr '17

Może nie myślisz 4 wymiarowo ?? https://d39a3h63xew422.cloudfront.net/wp-content/uploads/2016/04/21072139/the-back-to-the-future-delorean-now-lives-at-the-petersen-museum-1476934422032-1000x667.jpg27

Jak byś miał testy :

10
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000

--- to na prawde chciałbyś każdy przypadek liczyć od początku ??

Ja mam 2 pętle w programie - jedna jest od wczytywania danych . Powiedzenie do czego służy druga popsuło by tobie zabawę !

mariusz193
Apr '17
kapi3993

Skoro czasy pierwszej 20-ki są nie większe od 0.2 sekundy (łączny czas testów) to przekroczenie 2 sekund na jeden test to już sztuka :slight_smile: - lub niewłaściwy algorytm
więc zamiast optymalizować ten co napisałeś, pomyśl nad innym algorytmem

tomosatomos
Apr '17
1

Pisząc w pythonie spodziewam się raczej przekroczenia czasu niż złej odpowiedzi. Co do algorytmu to prawdopodobnie taki sam jak użył longinus. Tutaj kilka moich wyników:
IN:
29
200000
7000000
512
150
248
3000000
1000000
5001
2049
700000
800000
20
2
50002
300000
900000
400000
3
4000000
6000000
100000
1024
10123
500000
4
5000000
20344
600000
2000000

OUT:
2666686666700000
114333357833334500000
44870400
1136275
5115124
9000004500000500000
333333833333500000
41704177501
2869607425
114333578333450000
170666986666800000
2870
5
41672916975005
9000045000050000
243000405000150000
21333413333400000
14
21333341333334000000
72000018000001000000
333338333350000
358438400
345836482874
41666791666750000
30
41666679166667500000
2806853898420
72000180000100000
2666668666667000000

Czy jest tu błąd?

narbej
Apr '17

Patrze, patrze i jedyne co mi się nasuwa, to ....

Gdy dostaję WA [błędna odpowiedź], to warto jeszcze raz, albo kilka, uważnie przeczytać treść zadania. I taka jest w tym wypadku moja rada.

mietuffka
Apr '17

Witam przyjacielu, po pierwsze w tym zadaniu sam algorytm działa w czasie stałym. Więc całość działa w O(n), bo tyle potrzeba na wczytanie danych. Spróbuj jeszcze raz a ja radzę podejść matematycznie. Na pewno dasz radę!

kapi3993
Apr '17

Dziękuję wszystkim za zainteresowanie.
Pomyślałem nad innym algorytmem i zamiast pętli użyłem po prostu wzoru na sumę wyrazów tego ciągu rekurencyjnego co pozwoliło na pozbycie się jednej pętli (jestem początkujący, inaczej jeszcze nie potrafię) i zmniejszyło znacząco czas wykonywania kodu. Po tym zabiegu kod przeszedł test pozytywnie.
Jeszcze raz wszystkim dziękuję i serdecznie pozdrawiam.

mietuffka
Apr '17

kapi3993 Cieszę się, że przeszło. Mimo wszystko wystarczyło użyć wzoru na sumę kwadratów. n*(n+1)(2n+1) :smiley:

tomosatomos
Apr '17
narbej

Wiem o co Ci chodzi, q - liczba zapytań - nie wpisałem tego w poście pierwotnie. Teraz już poprawiłem i chodzi mi o to czy dla kolejnych liczb n oznaczających wymiar szachownicy (n x n) podaję dobre odpowiedzi.

szio
Apr '17

Niepotrzebnie pytasz o testy powyżej 1000000, bo autor nie ma takich wymagań.
Natomiast te testy do n = 1000000 dają takie same odpowiedzi u mnie.

loginus
Apr '17
tomosatomos

Twoje testy są za duże - i nie mieszczą się w żadnej standartowej strukturze do trzymania liczb - autor tak dobrał zakres danych że wynik mieści się w 64 bitowej liczbie bez znaku . Wszystkie testy dla liczb mniejszych od miliona mam takie same .

narbej
Apr '17

Kwestia podchwytliwych została chyba wyjaśniona? [po prostu nie ma takich].
Co do zgłoszenia: ID = 19203109, to tylko admini, autor zadania i Ty widzisz[widzą] kod zgłoszonego programu. Nikt inny nie widzi, więc trudno aby ktoś na forum, Ci poradził czy odpowiedział. Ale to też chyba się już wyjaśniło?
Masz dwa inne zgłoszenia [z przekroczonym limitem czasu] i możesz porównać je i sam stwierdzić, co popsułeś w tym jednym zgłoszeniu: http://pl.spoj.com/status/FR_07_06,tomosatomos/20