Discussion @ 1513. Lemon Tale @ Timus Online Judge

I use DP, but it works too slow. How to make it faster? (-) exwRabbits_AlMag(VNTU) 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? (-) Hao Hu (Ikki @ Nanjing University) 23 Dec 2006 13:23

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? (-) KirillB(Arkhangelsk - PomorSU) 23 Dec 2006 13:29

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? (-) exwRabbits_AlMag(VNTU) 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? (-) Hao Hu (Ikki @ Nanjing University) 23 Dec 2006 15:16

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? (-) exwRabbits_AlMag(VNTU) 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? (-) Hao Hu (Ikki @ Nanjing University) 23 Dec 2006 15:44

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? (-) 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? exwRabbits_AlMag(VNTU) 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? KirillB(Arkhangelsk - PomorSU) 23 Dec 2006 20:48

exwRabbits_AlMag(VNTU) wrote 23 December 2006 20:07

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? exwRabbits_AlMag(VNTU) 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? The Ninjas Walk Alone!!!! 24 Feb 2007 18:16

sizeof(Integer) depends on version of FPC

Re: Why sizeof(integer)=4? Denis Koshman 16 Jul 2008 18:12

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? (-) index 2 Mar 2016 13:38

Just use prefix sums to optimise dp.

Edited by author 02.03.2016 13:39

Discussion of Problem 1513. Lemon Tale