OJ Board

Hi!

I think that there are no tricky inputs in this task ( but I may be wrong )
If you didn't get your program AC look at this:

1. Check your program for test cases where k=1 or all the boxes are the same size...

2. Look carefully the next value shold be less ( not equal or less )
3. Look again at sorting -- while I was writin that program I had a small mistake there..
4. Check if you didn't forget about some boxes...

If your program is still WA. Send me the code on e-mail or write it in the post..

Good Luck

How this problem solve?
dynamic ?
hmm

sorry but I want large input data and output data.

my i/o data;

[input]
10 10
1 2 3 4 5 6 7 8 9 10
4 5 2 3 3 5 6 7 9 10
20 30 2 1 3 4 5 6 9 10
1 2 3 4 5 6 7 8 9 10
5 2 3 4 5 6 9 10 22 30
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
98 23 43 53 23 43 53 10 4 90
1 1 1 2 3 4 5 9 10 11

[output]
4
1 7 8 9

Algorithm solving was described some posts earlier. I've solved the task in the same way but i get WA. It passes all test i've found on this forum. What is wrong with it?
[cpp]
#include <iostream.h>
#include <string.h>

int d[31][10];
int map[30][30];

int N, M;

char less(int i, int j)
{
for (int k=0; k<N; k++)
if ( d[k]>=d[j][k] )
return 0;
return 1;
}

char equal(int i, int j)
{
for (int k=0; k<N; k++)
if ( d[k]!=d[j][k] )
return 0;
return 1;
}


int ml;
int mp[30];


int len[30];


int main()
{
int i, j, k, t, p;

while (cin>>M){
cin>>N;

for (i=0; i<M; i++){
for (j=0; j<N; j++)
cin>>d[j];
for (j=0; j<N; j++)
for (p=N-1; p>=j; p--)
if ( d[p] < d[p+1] ){
t = d[p];
d[p] = d[p+1];;
d[p+1] = t;
}
}


for (i=0; i<M; i++)
for (j=0; j<M; j++){
if (i!=j && less(i, j) )
map[j] = 1;
else
map[i][j] = 0;
}
ml=0;

for (int s=0; s<M; s++){
memset(len, 0, sizeof(len));
char found = 1;
len[s]=1;
while (found){
found = 0;
for (i=0; i<M; i++)
if (len[i]){
for (j=0; j<M; j++)
if (map[i][j] && len[j]<len[i]+map[i][j]){
len[j] = len[i]+map[i][j];
found = 1;
}
}
}
int l=0;
for (i=0; i<M; i++)
if (len[i]>len[l])
l=i;
int ll =len[l];
if (ll>ml){
ml=ll;
int prev = l;
i=ll;
mp[--i]=l;

for (; i>0;)
for (j=0; j<M; j++)
if (map[j][prev] && len[j]==len[prev]-map[j][prev] ){
mp[--i]=j;
prev = j;
break;
}
}
}
cout<<ml<<endl;
for (i=0; i<ml; i++)
cout<<mp[i]+1<<" ";
cout<<endl;
}
return 0;
}
[/cpp]

thx;
but i already passed 103 problem..
solution is DFS ^0^

Hi,
I try to solve this problem in these steps:
1) sort the numbers for each row
2) find the longest path

I know how to do the first step, but I have no clue how to achieve the second step. In my mind, i think i need to use DFS...but how? How can I connect the arrays (assume i am using two dimensional arrays to hold the numbers) to look like a graph??
Thanks in advance

To solve problem 103, some people said on the board about DP (Dynamic Programming).
How DP is used? Can anyone give me an example?
Thanks.

Here's a general idea of this problem:

1) The order of the dimensions isn't important, so feel free to sort the dimensions of the box as you read it in. Since the dimensionality doesn't exceed 10, insert sorting is an easy to use method.

2) I sorted my boxes also, based on the first dimension (after the dimensions for each box had been sorted). The only problem with this, is that you need to also keep track of the order the boxes were originally read in. I kept track of the order as an extra dimension, one that would not be compared when determining nesting ability.

3) Now that everything's sorted, DP comes into play. Need to find the longest string of nesting boxes.

You could try to find all the various combinations and brute force your way to a solution. But that's ugly. You don't want to go there. Instead, with DP, you gradually build the solution. With each box, you're not sure yet whether it is in the longest string, but you can determine the longest string involving that box up to that point, and you can determine the previous box in that list. I'll step you through how I chose to implement DP in my program.

For the first box in the sorted list, you know the length is 1, and there can't be any boxes that it nests into. (I sorted the boxes in descending order, you'll see why later) For box #2, you need to determine whether it can nest into box 1. If it can, the length at box #2 is 2, and box #1 is the end of the list, prior to adding box #2. For box #3, determine whether it can nest into box #2. If it can, add one to the length found for box#2, and consider box #2 the previous box. Whether it can or not, check box#1 and see if it can nest. If it can, does adding one to the length for box #1 give a longer length for box #3? If it does, store the new length and the new previous box. Etc.

Yes, this is still at the trivial level. There is some room for improving this algorithm. You can stop checking whether smaller boxes nest once the length for the sequence up to the current box is greater than the box number. So, if you're at box 20, and you've found that there is a length of at least 16 boxes that nest, including box 20, then you don't need to check boxes 15 and below, since they could not give you a longer nesting length.

Now, how do you reconstruct the longest list? I first did a scan through the list to find the longest overall length. With the boxes sorted in descending order, take one of the boxes that claims the longest overall length, output the length, output the read-in-order number of the box with the longest overall length (remember, the boxes were sorted in descending order, so as we worked our way through, the largest box is at the "start" of the list, the smallest is at the "end" of the list, and we're going to print the list in order, starting at the "end" and moving to the "start"). From there, find the previous box, and output it's read-in-order number, etc until there is no previous box.

So that's DP: instead of trying to enumerate all the possible cominations and determine which is the best, it determines at each step, what is the best possible solution up to that point. You must be able to determine a base case(s), and from that base case(s), a way to gradually build a solution. DP is generally used in "longest string" type cases.

David

See my response in this other post:
http://acm.uva.es/board/viewtopic.php?t=1406

Thanks, David!
Your answer helps me a lot!!

Hi.
I didn't clearly understand the problem.

For example: if I have box D={1,2,3,4,5}
Can I rearrange it D={1,3,5,2,4} or I have to keep order of dimensions?

I mean only
{2,3,4,5,1}
{3,4,5,1,2}
{4,5,1,2,3}
{5,1,2,3,4}
rearrangements are available?

I believe { 1, 4, 3, 5, 2 } is valid, ... the problem statement doesn't limit the rearrangement to rotate only.

-turuthok-

can anybody give me some test inputs for this question??

Hi, i seemed to get all the test inputs (including those in the forum) correct. Yet, I kept getting the W.A
Can anyone tell me what could be wrong???
Some kind soul, please help me!!

[cpp]
#include <iostream.h>

int n_dim, max_level;
int fit[30][30];
int ans[31];
int container[31];
int maxi(int ,int);

int main(void)
{
int n_box;
int i, j, k;
int c;
int hold, test;

int boxarr[30][10];

while (cin >> n_box >> n_dim)
{
for (i = 0; i < 30; i++)
{
for (j = 0; j < 10; j++)
{
boxarr[j] = 0;
}

for (j = 0; j < 31; j++)
{
fit[j] = 0;
}
ans = 0;
container = 0;
}



container[0] = 0;
for (i = 0; i < n_box; i++)
{
container[i+1] = 1;
for (j = 0; j < n_dim; j++)
{
cin >> boxarr[j];
}
}

for (i = 0; i < n_box; i++)
{
for (j = 0; j < (n_dim-1); j++)
{
for (k = 0; k < (n_dim-1); k++)
{
if (boxarr[k] > boxarr[k+1])
{
hold = boxarr[k];
boxarr[k] = boxarr[k+1];
boxarr[i][k+1] = hold;
}
}
}
}

for (k = 0; k < n_box; k++)
{
c = 0;
for (j = 0; j < n_box; j++)
{
test = 1;
for (i = 0; i < n_dim; i++)
{
if (boxarr[k][i] >= boxarr[j][i])
{
test = 0;
break;
}
}

if (test == 1)
{
fit[k][c] = (j+1);
c++;
}
}
}


max_level = 0;

for (i = 0; i < n_box; i++)
{
maxi(i, 0);
}

cout << max_level << endl;

for(i = 1; i <= max_level; i++)
{
cout << ans[i] << " ";
}
cout << endl;

}
return 0;
}



int maxi(int i, int level)
{

int kk, k, test;
int temp;

level++;

if (fit[i][0] == 0)
{
if (level > max_level)
{
max_level = level;

ans[level] = (i+1);
return 1;
}
return 0;
}
else
{
temp = 0;
for (kk = 0; kk < n_dim; kk++)
{
test = 0;
k = fit[i][kk];

if (k == 0)
{
break;
}

if(container[k] == 1)
{
container[k] = 0;
test = maxi(k-1, level);
container[k] = 1;
}
else
{continue;}

if (test == 1)
{
temp = 1;
ans[level] = i + 1;
}
}
}

if (temp == 1)
{
return 1;
}
else
{
return 0;
}
}



[/cpp]

in problem 103
i use the following algorithm
first i sort the dimensions of all the boxes
then i sort the boxes into lexicographic order depending on their dimensions
finally i use DP method
(similar to that used to find the longest monotonic subsequence)
and write the output
can u help me why i get WA
sorry for the length of the code kind ppl plz help me

i think your algo is wrong... it's a bit suspicious to sort the strings in lexicographic order....

sorting the dimensions of each cube is good, to see whether a box fits in another.

i just got accepted, my algo is:

build a N*N table like this:
tab[i,j] = 1 iff box i fits in box j
find longer path in the oriented graph described by this table... it's easy with recursion.
general rule:
if two boxes b1 b2 fit in box B, the longer path from B is max(b1,b2)+1
i'm not very clear sorry...

this two step attack should get this problem down in a few milliseconds

<-- who said i was kind? this is me in 9 2000 ... i look ugly and i'm a full time loser now