10559 - Blocks

[CDiMa]

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

[cyfra]

Hi!

Everything depends on your algorithm ....

You can reduce your running time (and complexity) very easy...

But first, could you write what algorithm do you use ..


Otherwise, I cannot help you

Good Luck

[CDiMa]

Hi!

Everything depends on your algorithm ....

Hi!

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...

You can reduce your running time (and complexity) very easy...

I refined already a bit my detection of low scores, but I fear I have to change completely
the approach to the prob.

Good Luck

Ciao!!!

Claudio

[BiK]

We can't think of an algorithm different from backtracking.

Cyfra, it seems that you devised a polynomial algorithm. Could you help us?

[cyfra]

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 )

[CDiMa]

Hi!

Yes I will help you, as much as I can

Great!

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

What is the value? The score obtained erasing the range of blocks?

If you think about it for a few moments you will find the method of filling this table...

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

This is sufficient to build the array but...

But of course it is too big to be filled in given time (and also too big to store it in the memory )...

... 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.

Any hints on this subject?

Ciao!!!

Claudio

[cyfra]

What is the value? The score obtained erasing the range of blocks?

Yes.. It is what I was thinking about...

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

... 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 )

Any hints on this subject?

See above


If this is still not enought then write another post ..


Best Regards

CYFRA

[BiK]

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

I don't understand this. Could you explain it more precisely please?

[CDiMa]

... 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...

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]

If this is still not enought then write another post ..


Best Regards

CYFRA

Here it is!

Ciao!!!

Claudio

[CDiMa]

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

I don't understand this. Could you explain it more precisely please?

I'm considering two ranges of blocks that are adiacent.
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

[cyfra]

Hi !

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 ??

[CDiMa]

Hi!

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 never thought that

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.

I think that the first one is basically wrong. There could be solutions with lesser
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.

PS.
If your program is still too slow, or you cannot understand what I wrote, than write another post..

No problem here, I think I got immediately the "vision"

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 ??

I 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!!!

Claudio

P.S. I'll be back monday, no need to hurry to answer

[cyfra]

Hi!

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.

Yes. You are right that the first one is wrong..

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]

[CDiMa]

Hi!!!

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..

Hmmm... what I'm still missing is how to build the array...

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]

( 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

[Joan Pi Sarr]

I have a program that seems to work fine, but I get W.A.
Can anyone provide some sample input-output?

Thanks