10559  Blocks
Moderator: Board moderators

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

 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
Answer: 5021
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
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 jth box at last and length of the last segment is k
Then
Computing Inf[i, j, k] for all possilbe k (0 < k <= l) is the main problem.
How I do it? Like this:
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.
Let Inf[i, j, k] be the highest score that I can get from i postion to j position clicking jth 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)
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
But it get TLE (
How can I improe it ? Please help me.
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 jth 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
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 jth 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
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.
bye,
ranjit.
Yes, I have seen you submision
But you write
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]
But you write
gush wroteplease refer to gush's post in the other thread(use search for 10559)
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]
hi
3dim 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 3d array(D[201][201][201]).
Can you please enlighten.
Thanx in advance.
bye,
ranjit
Can you please enlighten.
Thanx in advance.
bye,
ranjit
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 i1.
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 n1 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
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 i1.
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 n1 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
I used dynamic memory allocation to minimaze memory usage.
To speedup 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)
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)
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)