I use DP, but it works too slow. How to make it faster? (-)
Posted by
AlMag 23 Dec 2006 13:13
Edited by author 23.12.2006 13:14
Re: I use DP, but it works too slow. How to make it faster? (-)
I also have the same problem.
My algorithm runs in O(nk) time it will surely get TLE...
how to optimize it?
Re: I use DP, but it works too slow. How to make it faster? (-)
You can do it in O(n) with + and - long arithmetics
Re: I use DP, but it works too slow. How to make it faster? (-)
Posted by
AlMag 23 Dec 2006 14:26
Still TLE#18. I do it in O(n) with + and - long arithmetics.
Help, please!
Should I do long arothmetic by 4 numbers?
Мне делать длинную арифметику по 4 знака?
Мені робити довгу арифметику по 4 знака?
:)
Edited by author 23.12.2006 14:42
Re: I use DP, but it works too slow. How to make it faster? (-)
I got accepted, you can do long arithmetic with 8 numbers.
By the way I don't think using 4 numbers (10000) as radix will TLE.
:)
Re: I use DP, but it works too slow. How to make it faster? (-)
Posted by
AlMag 23 Dec 2006 15:29
Thanks, I have AC!
But a little question:
In my first solution (with 1 number) I used
array[1..10000][1..3200] of shortint;
than, (with 2 numbers) - array[1..10000][1..1600] of integer;
Isn't it the same? But in the second case I got MLE!
Whats wrong? Is sizeof(integer)=sizeof(longint)?
Thanks.
Re: I use DP, but it works too slow. How to make it faster? (-)
That depends on certain compilers.
Some compilers will tend to have sizeof(shortint) = sizeof(integer) or sizeof(integer) = sizeof(longint)...
that's where the problem lies...:(
Re: I use DP, but it works too slow. How to make it faster? (-)
Posted by
Kit 23 Dec 2006 17:33
shortint lies in range -128..127, so sizeof(shortint)=1, while sizeof(integer)=sizeof(longint)=4. So, second array eats double amount of memory in comparison with first one.
Why sizeof(integer)=4?
Posted by
AlMag 23 Dec 2006 20:07
integer lies in range -32768..32767.
It's 2 bytes.
Ans longint is in -2147483648..2147483647
It's 4 bytes.
Re: Why sizeof(integer)=4?
integer lies in range -32768..32767.
It's 2 bytes.
Ans longint is in -2147483648..2147483647
It's 4 bytes.
Do you use TP?
FreePascal 32-bit compiler
Integer - 32 bit
Read FAQ for differences
Re: Why sizeof(integer)=4?
Posted by
AlMag 23 Dec 2006 22:00
I use FP.
I write a program
var t:integer;
begin
t:=0;
writeln(sizeof(t));
end.
It shows 2.
var t:longint;
begin
t:=0;
writeln(sizeof(t));
end.
Shows 4.
Re: Why sizeof(integer)=4?
Posted by
Olly 24 Feb 2007 18:16
sizeof(Integer) depends on version of FPC
Re: Why sizeof(integer)=4?
I use O(n) DP with long arithmetics on 9 digits. Because 2*a-b falls in range -1e+9 ... +2e+9 for every digit.
Re: I use DP, but it works too slow. How to make it faster? (-)
Just use prefix sums to optimise dp.
Edited by author 02.03.2016 13:39