| ENG RUS | Timus Online Judge |
Discussion of Problem 1318. LogarithmProtsenko Sergey[Ivanovo SPU] WA on test 3. Please give me some tests [8] // Problem 1318. Logarithm 8 Sep 2004 15:51 Gheorghe Stefan Re: WA on test 3. Please give me some tests [4] // Problem 1318. Logarithm 8 Sep 2004 16:43 you cand generate tests yourself and compare with a brute force algorithm... Protsenko Sergey[Ivanovo SPU] Re: WA on test 3. Please give me some tests // Problem 1318. Logarithm 8 Sep 2004 23:30 I mean some tricky tests. Protsenko Sergey[Ivanovo SPU] I have AC! [2] // Problem 1318. Logarithm 9 Sep 2004 15:09 0.568 sec Alias (Alexander Prudaev) WA3 [1] // Problem 1318. Logarithm 8 Aug 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 Fetisov Alex [USTU Frogs] Re: WA3 // Problem 1318. Logarithm 30 Apr 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. Partisan Re: WA on test 3. Please give me some tests [2] // Problem 1318. Logarithm 14 Sep 2009 01:07 Try these: 2 0 0 0 8 0 0 0 9 --> 0 2 0 0 0 4 0 0 0 12 --> 0 Leonid (SLenik) Andrievskiy Re: WA on test 3. Please give me some tests [1] // Problem 1318. Logarithm 24 Aug 2011 00:25 Another test: 2 0 0 0 10 0 0 0 0 --> 2 Edited by author 24.08.2011 00:31 Ivan Tyamgin (TNU) Re: WA on test 3. Please give me some tests // Problem 1318. Logarithm 9 Apr 2014 22:15 2 0 0 0 0 4294967295 4294967295 4294967295 4294967295 --> 76 -XraY- Wrong test. // Problem 1318. Logarithm 30 Oct 2012 19:53 My program got Crash (assert), cause this test has some trash in the end. hoan TO ADMINS [2] // Problem 1318. Logarithm 9 Dec 2010 22:01 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 Sandro (USU) Re: TO ADMINS [1] // Problem 1318. Logarithm 11 Dec 2010 02:10 Your test was added. Your solution works 0.453 sec on it. :) hoan Re: thank you! // Problem 1318. Logarithm 12 Dec 2010 14:46 Victor Barinov (TNU) Help me, please! I get WA on test #10. (+) [1] // Problem 1318. Logarithm 1 Sep 2005 23:41 Maybe there any tricky input data? Thanks! Oracle[Lviv NU] Re: Help me, please! I get WA on test #10. (+) // Problem 1318. Logarithm 8 Aug 2009 20:20 I used scanf("%u%u%u%u") and got AC. But using gets instead (assuming that numbers are space separated) got WA10. Dmitry 'Diman_YES' Kovalioff Very interesting problem (+) [4] // Problem 1318. Logarithm 14 Sep 2004 15:30 ...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 :) Tolstobrov_Anatoliy[Ivanovo SPU] Re: Very interesting problem (+) [2] // Problem 1318. Logarithm 21 Aug 2005 21:56 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. Sergey M. Masloboev Re: Very interesting problem (+) [1] // Problem 1318. Logarithm 14 Sep 2006 14:02 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; } Al.Cash Re: Very interesting problem (+) // Problem 1318. Logarithm 8 Jun 2009 16:18 I think it's much more interesting to find O(n) solution. It is really beautiful. GaLL Re: Very interesting problem (+) // Problem 1318. Logarithm 31 Aug 2005 22:50 My solution uses additional array [65536] that helps to calculate int(log2()) of 16-bit numbers faster. GaLL 1318 C++ Accepted 0.406 314 КБ Fyodor Menshikov Java hint // Problem 1318. Logarithm 24 Mar 2009 13:57 Only one change in solution int mid = (low + high) / 2; - 1.0s int mid = (low + high) >> 1; - 0.6s More than impressive! tryit1 TLE on test case 8 // Problem 1318. Logarithm 26 Aug 2008 12:36 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. Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) What the bug in the testing system? [2] // Problem 1318. Logarithm 4 Jan 2008 01:14 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? Lomir Re: What the bug in the testing system? [1] // Problem 1318. Logarithm 4 Jan 2008 06:25 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. Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Re: Re: What the bug in the testing system? // Problem 1318. Logarithm 4 Jan 2008 16:38 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>") ? Maigo Akisame (maigoakisame@yahoo.com.cn) Help me, it's TLE #5. And another question inside. [3] // Problem 1318. Logarithm 3 Oct 2004 07:34 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. Aleksey (BMSTU IU7) Re: Help me, it's TLE #5. And another question inside. [2] // Problem 1318. Logarithm 3 Oct 2004 11:15 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 Dmitry 'Diman_YES' Kovalioff As I've written before, there is nothing difficult at all (+) [1] // Problem 1318. Logarithm 3 Oct 2004 14:47 No assembler, no data structure tricks. The problem can be easily solved via well-optimized precalc... Tolstobrov_Anatoliy[Ivanovo SPU] Re: As I've written before, there is nothing difficult at all (+) // Problem 1318. Logarithm 21 Aug 2005 22:02 Yes, Dmitry 'Diman_YES' Kovalioff the rights. 0.687s 281kb Geworm How to avoid TLE? [5] // Problem 1318. Logarithm 17 Apr 2004 08:45 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. Dmitry 'Diman_YES' Kovalioff Ultra-strict optimization (-) [4] // Problem 1318. Logarithm 17 Apr 2004 12:43 Geworm Re: Ultra-strict optimization (-) [3] // Problem 1318. Logarithm 19 Apr 2004 09:16 Do you mean optimize the simple O(n^2) solution or use an O(n) algorithm? Sergey Chernykh Re: Re: Ultra-strict optimization (-) [2] // Problem 1318. Logarithm 24 Aug 2004 22:49 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. Fat Peter Re: Re: Ultra-strict optimization (-) [1] // Problem 1318. Logarithm 24 Sep 2004 20:18 Can you tell me more about it?I got TLE...:( Sergey Chernykh Re: Re: Ultra-strict optimization (-) // Problem 1318. Logarithm 18 Oct 2004 16:30 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.
|