## 10559 - Blocks

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

### Re: 10559

[quote="Joan Pi Sarr

Joan Pi Sarr
New poster
Posts: 4
Joined: Fri Apr 11, 2003 5:29 pm
Thanks a lot, Claudio.
My program correctly solves your input in near 0 time, but I still have W.A.

Anyone knows some limit cases which may make a program fail?
Or perhaps is there something wrong in the description of the problem?

For instance, I assume that there is at least one box and at most 200
(no overflow is possible) ...

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
color[z] must be defferent from color[z + 1] and
color[z + 1] should be the same as color

thus, we can use 3-dim array to store the data.
D[a][l] : form a to b, the len of the last seg clicked out is l, and of course the color of the seg is color.

Der-Johng Sun
New poster
Posts: 7
Joined: Tue Dec 09, 2003 5:48 am
Location: Taiwan

### Re: 10559

Try This:

1
165
1 2 3 2 1 1 5 1 1 1 1 10 1 4 4 41 4 4 1 43 4 4 4 41 4 4 42 4 4 1 13 1 1 1 2 3 2 1 11 1 1 1 1 1 19 1 4 4 41 4 4 1 4 34 4 4 24 4 4 4 4 4 11 1 1 1 1 21 3 2 1 12 1 1 1 1 15 1 1 44 4 4 4 4 1 4 41 4 4 14 4 4 4 4 4 12 1 1 1 1 20 3 2 1 1 1 1 1 1 1 1 1 4 4 4 4 4 1 4 4 4 4 4 4 4 4 4 4 1 1 1 1 1 2 3 2 1 1 1 1 1 1 1 1 1 4 4 4 4 4 1 4 4 4 4 4 4 4 4 4 4 1 1 1 1

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 10559 TLE

I've got TimeLimitExceeded with my DP algorithm:

Let Inf[i, j, k] be the highest score that I can get from i postion to j position clicking j-th box at last and length of the last segment is k

Then

Code: Select all

`````` Inf[i, i, 1] = 1
Inf[i, i + 1, 1] = 2 if color[i] <> color[i + 1]
Inf[i, i + 1, 2] = 4 if color[i] = color[i + 1]

for l = 3 to n do
for i = 1 to n - l + 1 do
j = i + l - 1
Compute Inf[i, j, k] for all possilbe k (0 < k <= l)``````
Computing Inf[i, j, k] for all possilbe k (0 < k <= l) is the main problem.
How I do it? Like this:

Code: Select all

``````flag := 0;
for x := i to j - 1 do
if (color[x] <> color[x + 1]) and ((color[x + 1] = color[j]) or
((color[x] = color[j]) and (flag = 0))) then begin
compute inf[i, j, k] from all possible inf[i, x, k1], inf[x + 1, j, k2]
end
if color[x] <> color[x + 1] then flag = 1``````
And if [i..j] is a segment of the same color then inf[i, j, j - i + 1] = (j - i + 1)*(j - i + 1)

But it get TLE (

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### hi revenger

i have not yet solved this problem but have been working on it for quite a while.
Firstly,I didnt understand what exactly you are doing

"Let Inf[i, j, k] be the highest score that I can get from i postion to j position clicking j-th box at last and length of the last segment is k "
Can you explain that??

Are you grouping the blocks into segments based on colours?That should be desirable.And suppose a colour occurs only once you could straightaway remove that segment from the list of segments.Also while removing that, two adjacent segments might coalesce and it is probable that it is the only segment of that colour and hence once again you could remove it from the list.

After a few attempts at this problem,I have come to believe that it is solvable only in O(2^n) time and that ,only dp is of no use.I would be happy if somebody contradicts me.

Best of Luck and let me know if you got it ACed.

bye,
ranjit

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### hi

please refer to gush's post in the other thread(use search for 10559).it is of immense help to solve the problem and best of luck to everyone to solve this problem.this is a nice problem to illustrate the use of dp.

bye,
ranjit.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
Thanks, but I've got Accepted already. I used the same aproach as gush. But I wonder how to get Accepted under 1 sec ?! My solution work 1.652 sec and 4988 KB.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### hi

I too got it acc yesterday night and i submitted just after you(11 submissions in between).
Mine runs worse than yours both in terms of time and memory.Did u see the ranklist.I am the guy next to you.

Bye
ranjit

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
Yes, I have seen you submision
But you write
please refer to gush's post in the other thread(use search for 10559)
gush wrote
color[z] must be defferent from color[z + 1] and
color[z + 1] should be the same as color

This aproach is wrong. You also should consider then color[z] and color are the same. So, to calculate Inf[a, b] I consider all Inf[a, z], Inf[z + 1, b] where color[z + 1] = color; and the first Inf[a, z], Inf[z + 1, b] where color[z] = color

For example, if
n = 3
color[1] = 1
color[2] = 2
color[3] = 1

to calculate Inf[1, 3] I should consider not only Inf[1, 2], Inf[3, 3] but also Inf[1, 1], Inf[2, 3]

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
my approach to solving this problem was having a table like gush suggested,

a[j] === maximum score in reducing 0-i with the last color being the color of i and length j

it took the minimum memory!

but it takes lot of time.
i think that the idea mentioned in gush's post made the difference.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
But how you calculate a[j]? Please, explain it. I used 3-dim array to store maximum score in reducing i-j with the last color being the color of j and length k and another 3-dim array to speed-up seeking in the first array.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### hi

3-dim array and still your memory usage is so small ?Mine is 32256. I suppose that's the limit. Did you use a linked list or something similar rather than 3-d array(D[201][201][201]).
Can you please enlighten.

bye,
ranjit

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
i use the following idea to fill this two dimensional table

we can see that in the a[j] for j>length of the ith segment, the increase in the segment size came from some other previous segment of the same colour as the segment i.
so what i do is i go back and see a segment of the same color as the segment i, then i will see all possible maximum values of that segment, and add that to length of i the segment.

however, if k is the position where we find such a block, i needed the maximum score of
the segments k+1 to i-1.

i did not know how to find this.

so i ran my algorithm again and again on the segments t --> n, where t runs in a loop from n-1 to 0.
that is why it takes so much but repeatedly uses the same memory. (O(n^2))
the run time is O(n^3 . f) where f is the maximum repetetion the block segments.

i feel that there must be a O(n^2 f) solution. may be u used such solution??
can you tell more about your idea?
bye
abi

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
I used dynamic memory allocation to minimaze memory usage.

Code: Select all

``````type tarr = array[1..maxn]of word;
parr = ^tarr;
var inf : array[1..maxn, 1..maxn]of parr;

...

getmem(inf[i, j], (j - i + 1) shl 1)``````
To speed-up my solution I used 2 ideas:
1.) if inf[i, j, k] = 0 then you should not consider this element in computation of other elemets
2.) if inf[i, j, k] = c and inf[i, j, l] = t where (l < k) and (t <= c) you should not consider this element in computation of other elemets

So that you calculate Inf[i, j] from Inf[i, x], Inf[x+1, j] you shoukd consider only that Inf[i, x, k1], Inf[x + 1, j, k2] that satisfy 1.) and 2.)
So instead of (x - i + 1) * (j - x) operarions I do much less.

Abishek, I think that your idea is the key to the fastest solution. Also, I am sure that nothing will run less than in O(n^3)