| Show all threads Hide all threads Show all messages Hide all messages | | WA on test 3. Please give me some tests | Protsenko Sergey[Ivanovo SPU] | 1318. Logarithm | 9 Apr 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 Sep 2004 15:09 WA3 Alias (Alexander Prudaev) 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 Re: WA3 Fetisov Alex [USTU Frogs] 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. 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. Logarithm | 30 Oct 2012 19:53 | 1 | My program got Crash (assert), cause this test has some trash in the end. | | TO ADMINS | hoan | 1318. Logarithm | 12 Dec 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. Logarithm | 8 Aug 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. Logarithm | 8 Jun 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. Logarithm | 24 Mar 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. Logarithm | 26 Aug 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. Logarithm | 4 Jan 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. Logarithm | 21 Aug 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. Logarithm | 18 Oct 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. |
|
|
