10559 - Blocks

[CDiMa]

[quote="Joan Pi Sarr

[Joan Pi Sarr]

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]

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]

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

Answer: 5021

[Revenger]

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 (

How can I improe it ? Please help me.

[ranjit]

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]

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]

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]

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]

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]

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]

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]

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.
Thanx in advance.

bye,
ranjit

[abishek]

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]

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)