ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1513. Lemon Tale

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? (-)
Posted by 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? (-)
Posted by KIRILL(ArcSTU) 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? (-)
Posted by AlMag 23 Dec 2006 14:26
Still TLE#18. I do it in O(n) with + and - long arithmetics.
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? (-)
Posted by 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? (-)
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? (-)
Posted by 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? (-)
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?
Posted by KIRILL(ArcSTU) 23 Dec 2006 20:48
AlMag 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

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?
Posted by 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? (-)
Posted by Takanashi Rikka 2 Mar 2016 13:38
Just use prefix sums to optimise dp.

Edited by author 02.03.2016 13:39