10559 - Blocks
Moderator: Board moderators
10559 - Blocks
Are there any hints on how to reduce run time for this beast?
I improved significantly runtimes of my solution, but even some simple test cases I built take more than 10 seconds on my machine...
Ciao!!!
Claudio
I improved significantly runtimes of my solution, but even some simple test cases I built take more than 10 seconds on my machine...
Ciao!!!
Claudio
10559 Blocks problem TLE
Hi!cyfra wrote:Hi!
Everything depends on your algorithm ....
my algorithm is simple, and surely slow
Basically I read the data and construct a double linked list of segments so that's easy
to add and delete segments.
I have two helper functions that calculate the worst and potentially best score.
Then I recursively click each segment and try to early detect low scores...
I refined already a bit my detection of low scores, but I fear I have to change completelycyfra wrote:You can reduce your running time (and complexity) very easy...
the approach to the prob.
cyfra wrote:Good Luck
Ciao!!!
Claudio
Hi!
Yes I will help you, as much as I can
So I can give you a few hints :
1. Think about dynamic programming...
where you have to fill the array[1..n,1..n,1..n,1..n] ..
Descirption : if value of [a,b,c,d] = n then
it is possible to "erase" all the elements beetween position a and position b, the last "block" we erased had colour c and had d elements ....
If you think about it for a few moments you will find the method of filling this table...
But of course it is too big to be filled in given time (and also too big to store it in the memory )...
So here optimalization begins
I'll stop here.. I think that now you should think, what should be optimized, as not all the cells of this array will be used...
This is very good task, and it took me a few hours to find out and write down a good and fast program....
So be patient
Best Regards
Cyfra
PS.
But if you still don't know how to optimize it more.. (and it still get TLE) then write a post ( or PM )
Yes I will help you, as much as I can
So I can give you a few hints :
1. Think about dynamic programming...
where you have to fill the array[1..n,1..n,1..n,1..n] ..
Descirption : if value of [a,b,c,d] = n then
it is possible to "erase" all the elements beetween position a and position b, the last "block" we erased had colour c and had d elements ....
If you think about it for a few moments you will find the method of filling this table...
But of course it is too big to be filled in given time (and also too big to store it in the memory )...
So here optimalization begins
I'll stop here.. I think that now you should think, what should be optimized, as not all the cells of this array will be used...
This is very good task, and it took me a few hours to find out and write down a good and fast program....
So be patient
Best Regards
Cyfra
PS.
But if you still don't know how to optimize it more.. (and it still get TLE) then write a post ( or PM )
10559 Blocks problem TLE
Great!cyfra wrote:Hi!
Yes I will help you, as much as I can
What is the value? The score obtained erasing the range of blocks?cyfra wrote:So I can give you a few hints :
1. Think about dynamic programming...
where you have to fill the array[1..n,1..n,1..n,1..n] ..
Descirption : if value of [a,b,c,d] = n then
I understand that if I have two adiacent ranges of the same colour like this:cyfra wrote:If you think about it for a few moments you will find the method of filling this table...
[a, i, c, d]=k
[i+1, b, c, e]=l
then I get:
[a,b,c,d+e]=k+l+2*d*e
If I have adiacent ranges of different colours:
[a, i, c1, d1]=k
[i+1, b, c2, d2]=l
I get both of these:
[a, b, c1, d1]=k+l
[a, b, c2, d2]=k+l
This is sufficient to build the array but...
... while I can see several ways to store the computed tuples of values,cyfra wrote:But of course it is too big to be filled in given time (and also too big to store it in the memory )...
I can't figure what's the best data structure to use.
Any hints on this subject?
Ciao!!!
Claudio
Re: 10559 Blocks problem TLE
Yes.. It is what I was thinking about...CDiMa wrote:What is the value? The score obtained erasing the range of blocks?
CDiMa wrote:I understand that if I have two adiacent ranges of the same colour like this:
[a, i, c, d]=k
[i+1, b, c, e]=l
then I get:
[a,b,c,d+e]=k+l+2*d*e
If I have adiacent ranges of different colours:
[a, i, c1, d1]=k
[i+1, b, c2, d2]=l
I get both of these:
[a, b, c1, d1]=k+l
[a, b, c2, d2]=k+l
Yes.. It is a good solution ...
but too slow
CDiMa wrote:... while I can see several ways to store the computed tuples of values,
I can't figure what's the best data structure to use.
Hmm.. the best idea, will be a list with two fields : (color,number of last deleted)
It will reduce the memory that will be needed...
But with time..
another hint:
if you are counting values for interval a,b
do you really have to check all such z that a<z<b ??
( if you check only some of them you can reduce complexity very much )
See aboveCDiMa wrote:Any hints on this subject?
If this is still not enought then write another post ..
Best Regards
CYFRA
I don't understand this. Could you explain it more precisely please?I understand that if I have two adiacent ranges of the same colour like this:
[a, i, c, d]=k
[i+1, b, c, e]=l
then I get:
[a,b,c,d+e]=k+l+2*d*e
If I have adiacent ranges of different colours:
[a, i, c1, d1]=k
[i+1, b, c2, d2]=l
I get both of these:
[a, b, c1, d1]=k+l
[a, b, c2, d2]=k+l
Re: 10559 Blocks problem TLE
Hmmm, I still don't get it completely...cyfra wrote:CDiMa wrote:... while I can see several ways to store the computed tuples of values,
I can't figure what's the best data structure to use.
Hmm.. the best idea, will be a list with two fields : (color,number of last deleted)
It will reduce the memory that will be needed...
Do you mean something like this:
[c]
struct erased {
int colour;
int ndeleted;
int score;
struct erased * nextcolour;
};
struct erased *array[a];
[/c]
cyfra wrote:If this is still not enought then write another post ..
Best Regards
CYFRA
Here it is!
Ciao!!!
Claudio
Re: 10559 Blocks problem TLE
I'm considering two ranges of blocks that are adiacent.BiK wrote:I don't understand this. Could you explain it more precisely please?CDiMa wrote:I understand that if I have two adiacent ranges of the same colour like this:
[a, i, c, d]=k
[i+1, b, c, e]=l
then I get:
[a,b,c,d+e]=k+l+2*d*e
If I have adiacent ranges of different colours:
[a, i, c1, d1]=k
[i+1, b, c2, d2]=l
I get both of these:
[a, b, c1, d1]=k+l
[a, b, c2, d2]=k+l
Say that the first one starts from position a and ends at position i,
the second starts from position i+1 and ends at position b.
[a, i, c, d]=k means that some sequence of clicks exists that erases the range from a to i,
the last click erasing d blocks of colour c and obtaining the overall score k.
Similarly [i+1, b, c, e]=l means that some sequence of clicks exists that erases the range from i+1 to b, the last click erasing e blocks of colour c and obtaining the overall score l.
Since the colours last erased are the same we could imagine to click all
blocks between a and b leaving the d+e blocks of colour c last:
[a,b,c,d+e]
the score would be the sum of the previous plus the difference
(d+e)^2- (d^2+e^2) = 2*d*e
If the ranges were erased last clicking on different colours then you get the
same score indipendently of wich colour you last chose, so you get two
different tuples with the same score.
Using these rules plus the trivial ones of clicking a single segment of block of the same colour you can induce the complete (and huge) table from the starting configuration.
Hope this, although pedantic, is a bit clearer
Ciao!!!
Claudio
Re: 10559 Blocks problem TLE
Hi !
Yes that's was I was thinking about. .
So now, (as you can easily see) the memory you need is much much smaller than before..
Ok, so now it's time for next optimalization
So if you have to compute the value(s) of tab[a,b] then you can easily do
something like this :
[pascal] for z:=a+1 to b do
begin
{count solutions for [a,z-1] and [z,b] }
end;
[/pascal]
So this has complexity about O(n^3*m) where m is cost of concating the values of [a,z-1] and [z,b]
But you can reduce it easily by checking it only for some "z"...
Think again: Do you really have to check for all a<z<=b ??
(this is a very big optimization
Best Regads
CYFRA
PS.
If your program is still too slow, or you cannot understand what I wrote, than write another post..
PSS.
If you don't like my method of answering for posts, just write it..
I mean that I am answering step after step..
If it annoys you: write it to me (on e-mail or Private Message
But I personally think that this is the best way (especially for you, and everybody who will read it after you) to think about this problem for a while, and then (if it still doesn't work) move to next post..
What do you think about this ??
CDiMa wrote:Hmmm, I still don't get it completely...
Do you mean something like this:
[c]
struct erased {
int colour;
int ndeleted;
int score;
struct erased * nextcolour;
};
struct erased *array[a];
[/c]
Yes that's was I was thinking about. .
So now, (as you can easily see) the memory you need is much much smaller than before..
Ok, so now it's time for next optimalization
So if you have to compute the value(s) of tab[a,b] then you can easily do
something like this :
[pascal] for z:=a+1 to b do
begin
{count solutions for [a,z-1] and [z,b] }
end;
[/pascal]
So this has complexity about O(n^3*m) where m is cost of concating the values of [a,z-1] and [z,b]
But you can reduce it easily by checking it only for some "z"...
Think again: Do you really have to check for all a<z<=b ??
(this is a very big optimization
Best Regads
CYFRA
PS.
If your program is still too slow, or you cannot understand what I wrote, than write another post..
PSS.
If you don't like my method of answering for posts, just write it..
I mean that I am answering step after step..
If it annoys you: write it to me (on e-mail or Private Message
But I personally think that this is the best way (especially for you, and everybody who will read it after you) to think about this problem for a while, and then (if it still doesn't work) move to next post..
What do you think about this ??
Re: 10559 Blocks problem TLE
Hi!
I basically had two approaches in mind.
score but bigger count for the last colour clicked and so potentially hielding better
overall score.
For the second one I feared that the list of values may grow too much with the result
of beeing slow for concatenating subranges.
What I don't like is that we have incompatible "time zones"
Thank you very much for taking the time to help!!!
Claudio
P.S. I'll be back monday, no need to hurry to answer
I never thought thatcyfra wrote:So if you have to compute the value(s) of tab[a,b] then you can easily do
something like this :
[pascal] for z:=a+1 to b do
begin
{count solutions for [a,z-1] and [z,b] }
end;
[/pascal]
So this has complexity about O(n^3*m) where m is cost of concating the values of [a,z-1] and [z,b]
But you can reduce it easily by checking it only for some "z"...
Think again: Do you really have to check for all a<z<=b ??
I basically had two approaches in mind.
- 1) only store the best score for a colour
2) only consider (if they exist) z that have the same colour of a.
score but bigger count for the last colour clicked and so potentially hielding better
overall score.
For the second one I feared that the list of values may grow too much with the result
of beeing slow for concatenating subranges.
No problem here, I think I got immediately the "vision"cyfra wrote:PS.
If your program is still too slow, or you cannot understand what I wrote, than write another post..
I hate spoilers, so I like having the possibility of playing with new ideas for a while...cyfra wrote:PSS.
If you don't like my method of answering for posts, just write it..
I mean that I am answering step after step..
If it annoys you: write it to me (on e-mail or Private Message
But I personally think that this is the best way (especially for you, and everybody who will read it after you) to think about this problem for a while, and then (if it still doesn't work) move to next post..
What do you think about this ??
What I don't like is that we have incompatible "time zones"
Thank you very much for taking the time to help!!!
Claudio
P.S. I'll be back monday, no need to hurry to answer
Hi!
But the second one is what I thought about..
So if you have a to count the range from a to b ..
You can do it only for z that has the same color as a and b..
So you have to think whether you have to store values for all colors..
For example if color[a]=color=x ..
and color[z] = x ..
So do you have to compare all colors ??
Think about it
( but it is not so easy... you have to do something when color[a]<>color, but this quite easy (I hope )
I also hate such posts where someone subimts his code.. and say something like "I have WA, help me "
Unfortunately .... I can't do anything with that
No problem
But I hope that you will finally get AC
Best Regards
CYFRA[/quote]
Yes. You are right that the first one is wrong..I basically had two approaches in mind.
1) only store the best score for a colour
2) only consider (if they exist) z that have the same colour of a.
But the second one is what I thought about..
So if you have a to count the range from a to b ..
You can do it only for z that has the same color as a and b..
So you have to think whether you have to store values for all colors..
For example if color[a]=color=x ..
and color[z] = x ..
So do you have to compare all colors ??
Think about it
( but it is not so easy... you have to do something when color[a]<>color, but this quite easy (I hope )
hate spoilers, so I like having the possibility of playing with new ideas for a while...
I also hate such posts where someone subimts his code.. and say something like "I have WA, help me "
What I don't like is that we have incompatible "time zones"
Unfortunately .... I can't do anything with that
Thank you very much for taking the time to help!!!
No problem
But I hope that you will finally get AC
Best Regards
CYFRA[/quote]
Hi!!!
I was trying something like
[c]
for (w=1;w<numseg;w++) /* increasing width of ranges */
for(i=1;i+w<=numseg;i++) /* start of range */
if(array.colour==array[i+w][i+w].colour)
array[i+w] is built up from array, array[i+w][i+w] and array[i+1][i+w-1] with the same colour?
[/c]
If I don't know how to build the thing I can't think anything else than store all of them
Ciao!!!
Claudio
Hmmm... what I'm still missing is how to build the array...cyfra wrote:So if you have a to count the range from a to b ..
You can do it only for z that has the same color as a and b..
So you have to think whether you have to store values for all colors..
I was trying something like
[c]
for (w=1;w<numseg;w++) /* increasing width of ranges */
for(i=1;i+w<=numseg;i++) /* start of range */
if(array.colour==array[i+w][i+w].colour)
array[i+w] is built up from array, array[i+w][i+w] and array[i+1][i+w-1] with the same colour?
[/c]
cyfra wrote:( but it is not so easy... you have to do something when color[a]<>color, but this quite easy (I hope )
If I don't know how to build the thing I can't think anything else than store all of them
Ciao!!!
Claudio
-
- New poster
- Posts: 4
- Joined: Fri Apr 11, 2003 5:29 pm
10559
I have a program that seems to work fine, but I get W.A.
Can anyone provide some sample input-output?
Thanks
Can anyone provide some sample input-output?
Thanks