Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | WA on test 3. Please give me some tests | Protsenko Sergey[Ivanovo SPU] | 1318. Логарифм | 9 апр 2014 22:15 | 9 | you cand generate tests yourself and compare with a brute force algorithm... I mean some tricky tests. I have AC! Protsenko Sergey[Ivanovo SPU] 9 сен 2004 15:09 WA3 Alias (Alexander Prudaev) 8 авг 2007 20:58 My btute-force program gets WA3 by the way, some people have already solved this problem on java Edited by author 08.08.2007 21:11 Re: WA3 Fetisov Alex [USTU Frogs] 30 апр 2008 19:11 I had WA3 when didn't look through all the powers of 10 (38 is the last one) for my prebuild table. Try these: 2 0 0 0 8 0 0 0 9 --> 0 2 0 0 0 4 0 0 0 12 --> 0 Another test: 2 0 0 0 10 0 0 0 0 --> 2 Edited by author 24.08.2011 00:31 2 0 0 0 0 4294967295 4294967295 4294967295 4294967295 --> 76 | Wrong test. | -XraY- | 1318. Логарифм | 30 окт 2012 19:53 | 1 | My program got Crash (assert), cause this test has some trash in the end. | TO ADMINS | hoan | 1318. Логарифм | 12 дек 2010 14:46 | 3 | please add this test, i AC this problem in 0.812s, but my code answer to this code more than 1 second, in my computer, i think my computer is faster than the judge computer, sorry for my poor english.here is the test: 5000 4294967295 4294967295 4294967295 4294967295 (2500 times) 0 0 0 0 (2500 times) Edited by moderator 11.12.2010 02:07 Your test was added. Your solution works 0.453 sec on it. :) | Help me, please! I get WA on test #10. (+) | Victor Barinov (TNU) | 1318. Логарифм | 8 авг 2009 20:20 | 2 | Maybe there any tricky input data? Thanks! I used scanf("%u%u%u%u") and got AC. But using gets instead (assuming that numbers are space separated) got WA10. | Very interesting problem (+) | Dmitry 'Diman_YES' Kovalioff | 1318. Логарифм | 8 июн 2009 16:18 | 5 | ...And not as difficult as it seems to be. My program on Pascal gets AC within 0.796 sec without complicated optimizations and even without sorting, grouping, ets. Just some good precalc ideas realized properly :) Dima, I better 901327 21:51:38 21 авг 2005 Anatoliy 'Tolyan_NO' Tolstobroff 1318 Pascal Accepted 0.687 281 КБ Not use binaru searching use O(39), but cleaver. Optimized binary searching: no extras comparisons, no cycles 6 comparisons only !!! int Find( Tm_LargeNumber<> &n ) { if (n < Pow[16]) if (n < Pow[8]) if (n < Pow[4]) if (n < Pow[2]) if (n < Pow[1]) return 0; else return 1; else if (n < Pow[3]) return 2; else return 3; else if (n < Pow[6]) if (n < Pow[5]) return 4; else return 5; else if (n < Pow[7]) return 6; else return 7; else if (n < Pow[12]) if (n < Pow[10]) if (n < Pow[9]) return 8; else return 9; else if (n < Pow[11]) return 10; else return 11; else if (n < Pow[14]) if (n < Pow[13]) return 12; else return 13; else if (n < Pow[15]) return 14; else return 15; else if (n < Pow[32]) if (n < Pow[24]) if (n < Pow[20]) if (n < Pow[18]) if (n < Pow[17]) return 16; else return 17; else if (n < Pow[19]) return 18; else return 19; else if (n < Pow[22]) if (n < Pow[21]) return 20; else return 21; else if (n < Pow[23]) return 22; else return 23; else if (n < Pow[28]) if (n < Pow[26]) if (n < Pow[25]) return 24; else return 25; else if (n < Pow[27]) return 26; else return 27; else if (n < Pow[30]) if (n < Pow[29]) return 28; else return 29; else if (n < Pow[31]) return 30; else return 31; else if (n < Pow[36]) if (n < Pow[34]) if (n < Pow[33]) return 32; else return 33; else if (n < Pow[35]) return 34; else return 35; else if (n < Pow[37]) return 36; else if (n < Pow[38]) return 37; else return 38; } I think it's much more interesting to find O(n) solution. It is really beautiful. My solution uses additional array [65536] that helps to calculate int(log2()) of 16-bit numbers faster. GaLL 1318 C++ Accepted 0.406 314 КБ | Java hint | Fyodor Menshikov | 1318. Логарифм | 24 мар 2009 13:57 | 1 | Only one change in solution int mid = (low + high) / 2; - 1.0s int mid = (low + high) >> 1; - 0.6s More than impressive! | TLE on test case 8 | tryit1 | 1318. Логарифм | 26 авг 2008 12:36 | 1 | my algo was store double for table[4]=log10{ 2^96,2^64,2^32,0} in table. arr[i][4],arr[j][4] i from 1 to n j from i+1 to n k from 0 to 4 { a=arr[i][k],barr[j][k] if(!a) sum+= floor( log10(a) + table[k]),break; } This gets TLE on case 8 can someone tell me better algorithm or test cases. | What the bug in the testing system? | Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) | 1318. Логарифм | 4 янв 2008 16:38 | 3 | solving this problem i've found the interesting bug in the testing system: i submit the next code and get AC: #include <cstdio> #include <algorithm> using namespace std; [some code deleted :-] int l[600000],r[600000],x[600000],y[600000]; [some code deleted :-] int main() { for (int i=0; i<900000; ++i) y[i]=rand(); // i add this two lines of code to my AC program [some code deleted :-] return 0; } but i submit the next code and get Crash #1: #include <cstdio> #include <algorithm> using namespace std; int x[600000]; int y[600000]; int z[600000]; int main() { for (int i=0; i<900000; ++i) y[i]=rand(); printf("44"); return 0; } why? can anybody help me? There is no bug, except in your code. Second code is UB (undefind behavour). C++ standard do not define variable "possitions" in heap. As far as first one, I think it is also UB, however I am not sure about this. One time C++ optimizator just puts all 3 arrays "near". And second time, because of 3 different declatations, optimizator can make aligning to memory pages and put begining of each array into new page, this can make your program a little bit faster. But going out out bounds gets access violation now. Thanks a lot, but can somebody explain me what must I do to get "access violation" in similar situations? Maybe exists some tricks like #pragma comment(linker, "/stack:<new stack size>") ? | Help me, it's TLE #5. And another question inside. | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1318. Логарифм | 21 авг 2005 22:02 | 4 | Question: Why do I have to write for j:=1 to 4 do begin read(b); a[i,j]:=b; end; instead of read(a[i,1],a[i,2],a[i,3],a[i,4]); ? program ural1318; const maxn=5000; base=4294967296; maxe=38; type bignum=array[1..4]of int64; var e:array[0..maxe]of bignum; a:array[1..maxn]of bignum; n,i,j:word; ans,b:cardinal; function x(a,b:bignum):bignum; var i:byte; begin for i:=1 to 4 do x[i]:=a[i] xor b[i]; end; function smaller(a,b:bignum):boolean; var i:byte; begin for i:=1 to 4 do if a[i]<b[i] then begin smaller:=true;exit; end else if a[i]>b[i] then begin smaller:=false;exit; end; smaller:=false; end; function f(a:bignum):byte; var l,r,m:byte; begin l:=0;r:=maxe; repeat m:=(l+r+1) div 2; if smaller(a,e[m]) then r:=m-1 else l:=m; until l=r; f:=l; end; begin e[0,4]:=1; for i:=1 to maxe do for j:=4 downto 1 do begin inc(e[i,j],e[i-1,j]*10); if e[i,j]>=base then begin e[i,j-1]:=trunc(e[i,j]/base); dec(e[i,j],trunc(e[i,j-1]*base)); end; end; e[0,4]:=0; read(n); for i:=1 to n do begin for j:=1 to 4 do begin read(b); a[i,j]:=b; end; for j:=1 to i-1 do inc(ans,f(x(a[i],a[j]))); end; writeln(ans*2); end. In first: it is not correct to show this your solution (even wrong), please clear it, it already too bad. In second: for I:=1 to N do readln(A[I][0],A[I][1],A[I][2],A[I][3]); - is correct pascal-line, where type TNum=array[0..3] of longword var A:array[1..5000] of TNum; In third: to get AC your are to ULTRA-STRICT optimization. That meens some ASM-inline commands (bad way) or usual Pascal high-optimized code (depresive way). For example: my AC program (0.703 461 КБ) use two usual cycles (two "repeat", o(n*n/2)), and a LOG calculation code (about 650 lines). 650 lines was generated by my special generation program. This code consists only "IF" operator, "XOR" and ":=" operator. Some path of this code here: -----BEGIN LOG-FUNCTION---------------------- v:=A^[0]xor B^[0]; if v<1 then begin v:=A^[1]xor B^[1]; if v<5 then begin v:=A^[2]xor B^[2]; if v<2 then begin v:=A^[3]xor B^[3]; if v<1 then log:=0 else if v=1 then begin log:=0; end else begin if v<100000 then --....--------------------- if v<232830 then begin if v<232 then begin if v<23 then log:=10 else if v>23 then log:=11 else begin v:=A^[3]xor B^[3]; if v>=1215752192 then log:=11 else log:=10; begin end; end end else if v>232 then begin if v<2328 then begin if v<2328 then log:=12 else if v>2328 then log:=13 --....--------------------- then log:=log*2; To generate this code I use several recurse functions and binary search of course. Think better and get AC 1318(1/1) as my. Edited by author 03.10.2004 11:23 No assembler, no data structure tricks. The problem can be easily solved via well-optimized precalc... Yes, Dmitry 'Diman_YES' Kovalioff the rights. 0.687s 281kb | How to avoid TLE? | Geworm | 1318. Логарифм | 18 окт 2004 16:30 | 6 | I think O(n^2) algorithms will certainly lead to TLE. I tried to count how many results will be larger than 10,100,... and got an algorithm, and its complexity is O(800nlogn), still TLE. I heard that there was an O(n) algorithm, can anyone tell me how to do that? Thanks. Do you mean optimize the simple O(n^2) solution or use an O(n) algorithm? My ultra-optimized O(n^2) solution using some assembler in critical parts of code passed in 0.718 seconds. But I spend almost 2 hours for optimizing my code. Can you tell me more about it?I got TLE...:( You should use a table, which for every 2^k (0 <= k <= 127) keeps a value of Trunc(log10(2^k)). You should also keep a table with powers of 10 (10^0 .. 10^39). In the main loop of the program (which is straight-forward) you compute B = A[i] XOR A[j], then find the position k of the most significant bit of B (k is counted from zero). k is obtained using assembler instruction BSR (Bit Scan Reverse). At this point you know that 2^k <= B < 2^(k+1). Now, M := Trunc(log10(2^k)), and N := Trunc(log10(2^(k+1)). If B >= 10^N, then Trunc(log10(B))=N, else Trunc(log10(B))=M. Starting with this algorithm and optimizing it, you should get AC. |
|
|