## 10559 - Blocks

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
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 ..

Good Luck

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### 10559 Blocks problem TLE

cyfra wrote: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
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...
cyfra wrote: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.
cyfra wrote:Good Luck

Ciao!!!

Claudio

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
We can't think of an algorithm different from backtracking.

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

So I can give you a few hints :

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### 10559 Blocks problem TLE

cyfra wrote:Hi!

Great!
cyfra wrote:So I can give you a few hints :

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?
cyfra wrote: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...
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 )...
... 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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Re: 10559 Blocks problem TLE

CDiMa wrote:What is the value? The score obtained erasing the range of blocks?
Yes.. It is what I was thinking about...
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 )

CDiMa wrote:Any hints on this subject?
See above

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

Best Regards

CYFRA

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10559 Blocks problem TLE

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

cyfra wrote:If this is still not enought then write another post ..

Best Regards

CYFRA

Here it is!

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10559 Blocks problem TLE

BiK wrote:
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
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Re: 10559 Blocks problem TLE

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

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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10559 Blocks problem TLE

Hi!
cyfra 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 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.
cyfra wrote: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"

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..
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
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 ??

( 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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Hi!!!
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..
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]

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

Joan Pi Sarr
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