103 - Stacking Boxes

[jakabjr]

Allright, after some more searching I've found test that crack my code. If anyone gets WA, try these ones:

Code: Select all

input
8 3
1 10 1
8 8 8
4 6 6
7 5 7
5 2 1
1 2 1
6 2 4
5 5 3
output
5
6 8 3 4 2

input
17 4
859 397 577 913
757 501 912 171
836 991 761 899
647 446 709 426
295 211 586 775
750 619 733 153
192 999 205 89
264 552 958 328
309 705 412 596
94 569 98 520
529 849 162 453
299 3 766 227
748 539 511 820
778 562 725 523
497 200 103 880
903 737 701 423
813 788 691 857
output
6
10 9 4 13 17 3 

I know this has nothing to do with your SIGSEV, but it may help ones with WA or any need for test cases

[Hector]

Hi,

After getting TLE for my first couple of tries, I have found a problem case for time limit problem. If you are trying to solve this brute force, you might want to use this data to test your code.

Code: Select all

<input>
25 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
24
<output>
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

This one took around 1 minute on my P4-2.2GHz with brute force. Making input even longer, up to 30 boxes using same pattern, makes it much more time consuming (no I have not enough patience to time it ).

After a slight optimization, same input pattern with 30 boxes took less than 1sec to solve.

[late_nighter]

I has solved this problem 103 before . But due to recorrection it got a WA.

My algo is simple ..
I define a order of the boxes and sort them. Then I apply the longest increasing
subsequence algo to get the correct sequence.
The order in which I sort is if Box A can be placed inside Box B the A shud come
before in the order . It is topological sorting but I do it just with a simple sort routine.

Amal.

[Mohammad Mahmudur Rahman]

Your algo is identical to my AC one, so there should be no error there. You may try posting the code.

[jakabjr]

and maybe say what the correction was.
also, i first sort dimensions of boxes for each box, since they can be turned on any side, thus i find out if box A fits into box B.
how did u do?
the rest of the algo is ok, same as my AC

[late_nighter]

This is the code that is giving WA .

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

bool operator < (vector <int > a , vector <int> b)
{
for (int i = 0 ; i < a.size () -1; i ++ )
{
if (a >= b)
return false;
}

return true;

}

void printPath (vector <vector <int> > v , vector <int> par , int index)
{
if (par[index] == -1)
{
cout << v[index].back () <<" ";
return ;
}
printPath (v ,par, par[index]);
cout << v[index].back () << " ";
}

int main ()
{

int k,n,a,j,i;

while (cin >> k >> n )
{
vector <vector <int> > v (k);
for (i =0 ; i < k ;i ++ )
{
for (j = 0 ; j < n ; j ++ )
{
cin >> a;
v.push_back (a);
}
sort (v.begin () , v.end ());
v.push_back (i+1);
}

sort (v.begin () , v.end () );
/*
for (i = 0 ; i < k ; i ++ ,cout << endl)
for (j = 0 ; j < n ; j ++ )
cout << v[j] << " ";
*/

vector <int> arr (k);
vector <int> par (k);
arr[0] = 1;
par[0] = -1;
for (i = 1 ; i < k ; i ++ )
{
arr = 0;
par = -1;
for (j = i-1 ; j >= 0 ; j -- )
{
if (v[j] < v)
{
if (arr[j] +1 >= arr[i])
{
arr[i] = arr[j] +1;
par[i] = j;
}
}
}
}

int maxi;
cout << (maxi = * (max_element (arr.begin () , arr.end() ))) << endl;

int index = -1;
/* for (i = 0 ; i < k ; i ++ )
cout << arr[i]<< " ";
cout << endl;*/
for (i = 0 ;i < k ; i ++ )
if (maxi == arr[i])
{
index = i;
}


printPath (v , par, index);
cout << endl;
}
return 0;
}

[Hardi]

I have a problem with my solution.
Here's what my program does:
1. reads the input and stores it into an array
2. It will put the numbers increasingly in the same array:
if the input is
--- /*start of input*/
1 6
1 8 3 2 10 20
--- /*end of input*/

So:
1 2 3 8 10 20

then it will compare all the boxes and store the data of which box is bigger than which box.

e.g. if the input is:
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

then the "which box is bigger looks like this:
it means, that
1 /*box number 1 is the smallest*/
2 7 /*box number 2 is bigger than box nr. 8*/
3 1 2 7 /*3 is bigger than 1 2 and 7*/
4 7 /* and so on*/
5 1 2 7
6 1 2 4 5 7
7
8 1 2 5 7

the it will call a recursive function which finds the longest possible string.

My source code is about 200 lines(I commented it alot) and I think it is no point to examine it.

I want to know, if there is a logical error in my logic or not.

[Gaolious]

use the DP.

but, 'sorting' is important to use DP algorithm


first,

input : 1 4 3 2
after sort : 1 2 3 4

and,

second sort is

input 1 : 1 2 4 4
input 2 : 1 2 2 4
input 3 : 1 2 3 4

after sort :

data structure is
DATA[ 1 ] = 1 2 2 4
DATA[ 2 ] = 1 2 3 4
DATA[ 3 ] = 1 2 4 4


and use the DP algorithm

i hope you got AC[/b]

[Hardi]

Hy.
I just can't understand what's wrong.
I was writing a solution for problem 103.
I compiled the program and it seems to read the input wrongly.

Code: Select all

/*******************************
 *

[chunyi81]

Hi,

Your code crashes when I ran it with input "3 3" and not the output you stated in your post. You used signed short.

"%d" is used for signed integers (signed int or int, both are the same)

Try with cin and cout from iostream library instead.

Code: Select all

cin >> K >> D;         
cout << "K = " << K << "; D = " << D << endl;

I am not exactly sure how to make your code work with scanf/printf though. cin/cout works with almost all primitive data types.

[Hardi]

Thank you for your answer.
I'll try to figure out a way to read from input with scanf. cin is slower than scanf.

[Hardi]

What does that DP abbreviation mean and how does that algorithm work.

Now if I understood the problem correctly, I have to rearrange the measurments of 1 box so that it will fit into a bigger box, which measurements are bigger than the box, whose measurements I changed.

As I can see, you sort the boxes increasingly
1 2 2 4
1 2 3 4
1 2 4 4

And then I should check all the array DATA [1..3]
so that if DATA[2] has a side, which is <= with one of DATA[1] sides, then I will eliminate DATA[2]. I do the same with all boxes which meet the condition.
And In the end, I just output the remaining boxes indexes and the number of those indexes in the front.
True?

[Hardi]

Ok, here's the deal.
I rewrote my code and It got Accepted.

"Your C++ program has solved Ok the problem 103 (Stacking Boxes)
in 0.436 seconds using as much as 392 kbytes of virtual memory.
Congratulations!"

My code:

Code: Select all

/*******************************
 *

[misof]

One problem with your code is that you don't compile with warnings enabled and/or don't read them. The format strings you used for scanf are wrong. The correct format string for a signed short is %hd, not %d. On a 32-bit platform in gcc, long is the same as int, unsigned long == unsigned int and the correct format string is %u, not %d.

As a side note, there is really no need to use signed shorts instead of ints... there is plenty of memory available, ints enable you to store larger numbers and they are even a bit faster.

[Krzysztof Duleba]

int type is not faster than short at all. Addition might be just as fast, but *, / and % are slower.