| ENG RUS | Timus Online Judge |
Обсуждение задачи 1318. ЛогарифмProtsenko Sergey[Ivanovo SPU] WA on test 3. Please give me some tests [8] // Задача 1318. Логарифм 8 сен 2004 15:51 Gheorghe Stefan Re: WA on test 3. Please give me some tests [4] // Задача 1318. Логарифм 8 сен 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 // Задача 1318. Логарифм 8 сен 2004 23:30 I mean some tricky tests. Protsenko Sergey[Ivanovo SPU] I have AC! [2] // Задача 1318. Логарифм 9 сен 2004 15:09 0.568 sec Alias (Alexander Prudaev) WA3 [1] // Задача 1318. Логарифм 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 Fetisov Alex [USTU Frogs] Re: WA3 // Задача 1318. Логарифм 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. Partisan Re: WA on test 3. Please give me some tests [2] // Задача 1318. Логарифм 14 сен 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] // Задача 1318. Логарифм 24 авг 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 // Задача 1318. Логарифм 9 апр 2014 22:15 2 0 0 0 0 4294967295 4294967295 4294967295 4294967295 --> 76 -XraY- Wrong test. // Задача 1318. Логарифм 30 окт 2012 19:53 My program got Crash (assert), cause this test has some trash in the end. hoan TO ADMINS [2] // Задача 1318. Логарифм 9 дек 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] // Задача 1318. Логарифм 11 дек 2010 02:10 Your test was added. Your solution works 0.453 sec on it. :) hoan Re: thank you! // Задача 1318. Логарифм 12 дек 2010 14:46 Victor Barinov (TNU) Help me, please! I get WA on test #10. (+) [1] // Задача 1318. Логарифм 1 сен 2005 23:41 Maybe there any tricky input data? Thanks! Oracle[Lviv NU] Re: Help me, please! I get WA on test #10. (+) // Задача 1318. Логарифм 8 авг 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] // Задача 1318. Логарифм 14 сен 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] // Задача 1318. Логарифм 21 авг 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] // Задача 1318. Логарифм 14 сен 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 (+) // Задача 1318. Логарифм 8 июн 2009 16:18 I think it's much more interesting to find O(n) solution. It is really beautiful. GaLL Re: Very interesting problem (+) // Задача 1318. Логарифм 31 авг 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 // Задача 1318. Логарифм 24 мар 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 // Задача 1318. Логарифм 26 авг 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] // Задача 1318. Логарифм 4 янв 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] // Задача 1318. Логарифм 4 янв 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? // Задача 1318. Логарифм 4 янв 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] // Задача 1318. Логарифм 3 окт 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] // Задача 1318. Логарифм 3 окт 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] // Задача 1318. Логарифм 3 окт 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 (+) // Задача 1318. Логарифм 21 авг 2005 22:02 Yes, Dmitry 'Diman_YES' Kovalioff the rights. 0.687s 281kb Geworm How to avoid TLE? [5] // Задача 1318. Логарифм 17 апр 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] // Задача 1318. Логарифм 17 апр 2004 12:43 Geworm Re: Ultra-strict optimization (-) [3] // Задача 1318. Логарифм 19 апр 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] // Задача 1318. Логарифм 24 авг 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] // Задача 1318. Логарифм 24 сен 2004 20:18 Can you tell me more about it?I got TLE...:( Sergey Chernykh Re: Re: Ultra-strict optimization (-) // Задача 1318. Логарифм 18 окт 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.
|