I improved significantly runtimes of my solution, but even some simple test cases I built take more than 10 seconds
![:(](./images/smilies/icon_frown.gif)
Ciao!!!
Claudio
Moderator: Board moderators
Hi!cyfra wrote:Hi!
Everything depends on your algorithm ....
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...
cyfra wrote:Good Luck
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...
... 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 )...
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
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.
See aboveCDiMa wrote:Any hints on this subject?![]()
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
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...
cyfra wrote:If this is still not enought then write another post ..
Best Regards
CYFRA
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
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]
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 ??
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 ??
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.
hate spoilers, so I like having the possibility of playing with new ideas for a while...
What I don't like is that we have incompatible "time zones"
Thank you very much for taking the time to help!!!
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..
cyfra wrote:( but it is not so easy... you have to do something when color[a]<>color, but this quite easy (I hope)