103 - Stacking Boxes

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 103 problem ...

Post by brianfry713 » Mon Oct 01, 2012 9:30 pm

Look up the Longest Increasing Subsequence algorithm.
Check input and AC output for thousands of problems on uDebug!

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 103 problem ...

Post by amishera » Sat Oct 20, 2012 6:31 am

Hi I am getting verdict as "blank". What does it mean? I am waiting for more than 24 hours to get a verdict.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 103 problem ...

Post by brianfry713 » Mon Oct 22, 2012 9:24 pm

The judge could have been down, try resubmitting.
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

help about WA on #103

Post by happyson10 » Sun Nov 18, 2012 8:32 am

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;


class Main
{

/*
* Time O( ) Space O( )
*/
public void stackBoxes(int[][] boxes, int rows) {
//init
HashMap<int[], Integer> hm = new HashMap<int[], Integer>();
ArrayList<int[]> list = new ArrayList<int[]>();
for(int row=0; row < rows; row ++){
Arrays.sort(boxes[row]);

//list.add(boxes[row]);
addInSorted(list, boxes[row]);
hm.put(boxes[row], row);
}

//Collections.sort(list, new boxComparator());

//DP, get the LIS
int[] dp = new int[rows]; //dp is the LIS of boxes[0--i], the default value is 0
int max = 0;
for(int i = 1; i<rows; i++ ){
for (int j = i-1; j >=0; j--) {
if (dp < dp[j] + 1 && isNestIn(list.get(j), list.get(i)))
dp = dp[j] + 1;

}
max = Math.max(max, dp);
}

//output
System.out.println(max + 1);

int i=rows - 1;
for( ;i>=0; i--){
if(dp == max)
break;
}
Stack<Integer> stack = new Stack<Integer>();
for( ; i>=0; i--){
if(dp == max ){
stack.add(hm.get(list.get(i)));
max --;
}
}

StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop() + 1);
sb.append(" ");
}

System.out.println( sb.substring(0, sb.length() - 1).toString() );
}

/**
* @return true if box1 nests in box2, or false
*/
private boolean isNestIn(int[] box1, int[] box2)
{
//if(box1.length != box2.length)
// return false;

for(int i=0; i<box1.length; i++){
if(box1 >= box2 )
return false;
}

return true;
}

private void addInSorted(ArrayList<int[]> list, int[] box){
if(list.size() == 0){
list.add(box);
return;
}

int col=0, row = 0;
for( ; col< box.length && row < list.size(); ){
if(box[col] > list.get(row)[col] ){
row ++;
}else if (box[col] == list.get(row)[col]) {
col ++;
}else
break;

}

list.add(row, box);
}




/**
* @param args
*/
public static void main(String[] args) {
Main sv = new Main();
Scanner in = new Scanner(new BufferedInputStream(System.in), "UTF-8");

try{
while(in.hasNext()){
int rows = in.nextInt();
int cols = in.nextInt();
int[][] boxes = new int[rows][cols];

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
boxes[j] = in.nextInt();

}
}

sv.stackBoxes(boxes, rows);
}
}catch(Exception e){
//e.printStackTrace();
}finally{
in.close();
}

}

}
Last edited by happyson10 on Sun Nov 18, 2012 9:43 am, edited 1 time in total.

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: help about WA on #103

Post by happyson10 » Sun Nov 18, 2012 8:39 am

in my code, i don't think box D = (2,6) nests in the box E = (3,6).

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: help about WA on #103

Post by happyson10 » Mon Nov 19, 2012 7:41 am

i have fix this issue.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: help about WA on #103

Post by brianfry713 » Tue Nov 20, 2012 2:51 am

Your output for the second sample input is:
4
1 2 3 6

However box 1:
5 2 20 1 30 10
will not fit inside box 2:
23 15 7 9 11 3

Sort box 1 to get:
1 2 5 10 20 30
Sort box 2:
3 7 9 11 15 23
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: help about WA on #103

Post by happyson10 » Wed Nov 21, 2012 4:11 am

thanks
i have found the issue and get AC, it's in "output part"

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

class Main
{

/*
* Time O( rows* rows*cols ) Space O( )
*/
public void stackBoxes(int[][] boxes, int rows) {
//init
HashMap<int[], Integer> hm = new HashMap<int[], Integer>();
ArrayList<int[]> list = new ArrayList<int[]>();
for(int row=0; row < rows; row ++){
Arrays.sort(boxes[row]);

//list.add(boxes[row]);
addInSorted(list, boxes[row]);
hm.put(boxes[row], row);
}

//Collections.sort(list, new boxComparator());

//DP, get the LIS
int[] dp = new int[rows]; //dp is the LIS of boxes[0--i]
String[] path = new String[rows];
for(int i=0; i<rows; i++)
path = String.valueOf(hm.get(list.get(i)) + 1);


int max = 0;
for(int i = 1; i<rows; i++ ){
for (int j = i-1; j >=0; j--) {
if (dp < dp[j] + 1 && isNestIn(list.get(j), list.get(i))) {
dp = dp[j] + 1;
path = path[j] + " " + (hm.get(list.get(i)) + 1);
}
}
max = Math.max(max, dp);
}

//output
System.out.println(max + 1);

int i=rows - 1;
for( ;i>=0; i--){
if(dp == max){
System.out.println(path);
break;
}
}

}

/**
* @return true if box1 nests in box2, or false
*/
private boolean isNestIn(int[] box1, int[] box2)
{
//if(box1.length != box2.length)
// return false;

for(int i=0; i<box1.length; i++){
if(box1 >= box2 )
return false;
}

return true;
}

private void addInSorted(ArrayList<int[]> list, int[] box){
if(list.size() == 0){
list.add(box);
return;
}

int col=0, row = 0;
for( ; col< box.length && row < list.size(); ){
if(box[col] > list.get(row)[col] ){
row ++;
}else if (box[col] == list.get(row)[col]) {
col ++;
}else
break;

}

list.add(row, box);
}

// class boxComparator implements Comparator<int[]>{
// public int compare(int[] box1, int[] box2)
// {
//
// for(int i=0; i<box1.length; i++){
// if(box1[i] < box2[i] ){
// return -1;
// }
// }
//
// return 1;
// }
// }

/**
* @param args
*/
public static void main(String[] args) {
Main sv = new Main();
Scanner in = new Scanner(new BufferedInputStream(System.in), "UTF-8");

try{
while(in.hasNext()){
int rows = in.nextInt();
int cols = in.nextInt();
int[][] boxes = new int[rows][cols];

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
boxes[i][j] = in.nextInt();

}
}

sv.stackBoxes(boxes, rows);
}
}catch(Exception e){
//e.printStackTrace();
}finally{
in.close();
}

}

}

Fedaykin
New poster
Posts: 6
Joined: Sun Dec 09, 2012 9:27 pm

103 longest inc seq question

Post by Fedaykin » Sun Dec 16, 2012 2:22 am

http://en.wikipedia.org/wiki/Longest_in ... ubsequence
I understand how the algorithm works with integer values that are either greater or lesser than other values. I don't see how that algorithm works with boxes that can't nest inside others.

for example with integers { 3 , 6 , 1 , 2 , 5 , 4}
for 1 to 5
m = { 3 }
m = { 3 , 6 }
m = { 1 , 6 }
m = { 1 , 2 }
m = { 1 , 2 , 5 }
m = { 1 , 2 , 4 }
so the longest increasing sequence has magnitude three.

how does this work with boxes in the test case...

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

m = { 7 }
m = ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 103 longest inc seq question

Post by brianfry713 » Tue Dec 18, 2012 12:12 am

Check input and AC output for thousands of problems on uDebug!

Fedaykin
New poster
Posts: 6
Joined: Sun Dec 09, 2012 9:27 pm

Re: 103 longest inc seq question

Post by Fedaykin » Tue Dec 18, 2012 1:18 am

I had no idea this existed :o

talz13
New poster
Posts: 5
Joined: Sat Oct 18, 2008 7:20 pm

WA on problem 103

Post by talz13 » Sun Jun 23, 2013 3:42 am

I'm getting WA on problem 103... I am testing with the sample input from the algorithmist page

http://algorithmist.com/index.php/UVa_103

And here is my output:

Code: Select all

5
3 1 2 4 5
4
7 2 5 8
1
1
5
4 5 1 2 3
13
1 7 8 9 10 26 12 11 13 17 19 18 20
There's no hanging endlines or whitespace AFAIK, and my solutions appear to be valid possible solutions for the sample input from algorithmist. The 'freopen("sampleInput.txt", "r", stdin);' line is just to get netbeans to run my program with the sample input file, and I removed it when submitting.

Code: Select all

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

#include <cstdio>

using namespace std;

/*
 *
 */

class Box {
public:
    int boxNumber;
    vector<int> dimensions;
};

typedef vector<Box*>::iterator boxIter;

vector<Box*> stackBoxes(vector<Box*> boxes);
vector<Box*> stackBoxRecurse(boxIter begin, boxIter end, vector<Box*> currentStack, int level);
bool boxFit(Box* a, Box* b);
bool boxSort(Box* a, Box* b);
void display(vector<Box*> boxes);
void finalDisplay(vector<Box*> boxes);

int main(int argc, char** argv) {

    freopen("sampleInput.txt", "r", stdin);

    int numBoxes = 0;
    int dimensions = 0;
    bool first = true;
    while (cin >> numBoxes >> dimensions) {
        if (!first)
            cout << endl;
        vector<Box*> boxes;
        for (int i = 0; i < numBoxes; i++) {
            Box* tempBox = new Box();
            tempBox->boxNumber = i + 1;
            int tempInt;
            for (int j = 0; j < dimensions; j++) {
                cin >> tempInt;
                tempBox->dimensions.push_back(tempInt);
            }
            std::sort(tempBox->dimensions.begin(), tempBox->dimensions.end());
            boxes.push_back(tempBox);
        }
//                display(boxes);
        sort(boxes.begin(), boxes.end(), boxSort);
//                cout << endl;
//                display(boxes);
        vector<Box*> stackedBoxes = stackBoxes(boxes);
        finalDisplay(stackedBoxes);
        first = false;
    }
    return 0;
}

vector<Box*> stackBoxes(vector<Box*> boxes) {
    int maxStack = 0;
    vector<Box*> maxStackVector;
    // Start with a box on the stack, have to try each box first:
    //    for (int i = boxes.size() - 1; i >= 0; i--) {
    for (int i = 0; i < boxes.size(); i++) {
        vector<Box*> boxStack;
        boxStack.push_back(boxes[i]);
        vector<Box*> tempMaxStackVector;
//        cout << "Starting with " << boxes[i]->boxNumber << endl;
        tempMaxStackVector = stackBoxRecurse(boxes.begin() + i + 1, boxes.end(), boxStack, 0);
        if (tempMaxStackVector.size() > maxStack) {
//            cout << "Larger!" << endl;
            maxStack = tempMaxStackVector.size();
            maxStackVector = tempMaxStackVector;
        }
    }
    return maxStackVector;
}

vector<Box*> stackBoxRecurse(boxIter begin, boxIter end, vector<Box*> currentStack, int level) {
    vector<Box*> internalStack = currentStack;
    for (boxIter cur = begin; cur < end; cur++) {
        vector<Box*> tempStack = currentStack;
//        for (int i = 0; i < level; i++)
//            cout << " ";
//        cout << "Trying to add " << ((Box*)*cur)->boxNumber << "..." << endl;
        if (boxFit(tempStack.back(), *cur)) {
//            cout << "Adding " << (*cur)->boxNumber << " to tempStack!" << endl;
            tempStack.push_back(*cur);
//            cout << "tempStack: ";
//            for (int i = 0; i < tempStack.size(); i++) {
//                cout << " " << tempStack[i]->boxNumber;
//            }
//            cout << endl;
            tempStack = stackBoxRecurse(++cur, end, tempStack, level + 1);
        }
        if (tempStack.size() > internalStack.size()) {
//            cout << "Max increased to " << tempStack.size() << "!" << endl;
            internalStack = tempStack;
        }
    }
//    cout << "Internal stack is " << internalStack.size() << " blocks!" << endl;
//    finalDisplay(internalStack);
    return internalStack;
}

bool boxFit(Box* a, Box* b) {
    for (int i = 0; i < a->dimensions.size(); i++) {
        if (a->dimensions[i] >= b->dimensions[i])
            return false;
    }
    return true;
}

bool boxSort(Box* a, Box* b) {
    int smallerCounter = 0;
    bool returnValue = false;
    for (int i = 0; i < a->dimensions.size(); i++) {
        if (a->dimensions[i] > b->dimensions[i]) {
            break;
        } else if (a->dimensions[i] < b->dimensions[i])
            smallerCounter++;
    }
    if (smallerCounter > 0)
        returnValue = true;
    return returnValue;
}

void display(vector<Box*> boxes) {
    for (int i = 0; i < boxes.size(); i++) {
        cout << "Box " << boxes[i]->boxNumber << ":";
        for (int j = 0; j < boxes[i]->dimensions.size(); j++) {
            cout << " " << boxes[i]->dimensions[j];
        }
        cout << endl;
    }
}

void finalDisplay(vector<Box*> boxes) {
    cout << boxes.size() << endl;
    //    cout << boxes[boxes.size() - 1]->boxNumber;
    cout << boxes[0]->boxNumber;
    //    for (int i = boxes.size() - 2; i >= 0; i--) {
    for (int i = 1; i < boxes.size(); i++) {
        cout << " " << boxes[i]->boxNumber;
    }
    //    cout << endl;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA on problem 103

Post by brianfry713 » Mon Jun 24, 2013 11:55 pm

Print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

talz13
New poster
Posts: 5
Joined: Sat Oct 18, 2008 7:20 pm

Re: WA on problem 103

Post by talz13 » Tue Jun 25, 2013 12:03 am

K, I stopped suppressing the newline at the end of the output, but still got WA.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA on problem 103

Post by brianfry713 » Wed Jun 26, 2013 12:59 am

Input:

Code: Select all

22 3
44 71 27
37 91 79
96 10 74
52 35 19
40 98 85
67 79 43
93 29 13
37 87 17
75 24 74
36 31 11
89 80 84
75 31 39
20 88 87
14 89 70
25 30 93
28 20 72
11 30 78
87 36 50
54 72 21
20 28 57
68 50 25
80 45 58
5 2
35 45
72 49
74 75
65 84
96 44
29 1
54
13
74
42
93
72
65
37
20
97
13
77
43
93
17
44
38
54
48
98
63
40
85
81
92
62
72
96
58
26 6
65 41 49 98 87 92
13 26 17 30 75 65
72 36 59 28 63 69
56 11 47 95 77 84
81 98 69 31 87 60
27 14 52 68 32 68
29 97 92 13 48 95
19 25 53 38 79 14
84 38 62 58 33 17
32 83 76 48 81 23
33 79 96 52 56 28
10 79 55 18 15 91
39 69 97 98 48 14
52 23 79 18 39 72
43 68 88 93 15 55
10 89 44 81 50 58
12 74 39 22 25 63
65 39 94 59 63 16
44 28 89 72 52 80
76 53 80 42 77 35
91 33 78 14 77 20
22 14 99 98 35 55
12 30 26 83 12 75
83 45 64 23 66 85
46 10 88 27 19 58
83 73 51 89 15 93
15 6
82 64 50 42 36 40
35 39 58 63 47 29
57 77 49 37 67 73
59 13 62 88 29 57
10 99 50 30 17 93
80 55 74 79 14 45
46 40 55 98 91 13
72 87 27 88 98 89
33 32 12 30 86 45
45 51 88 77 92 20
50 12 42 88 35 87
62 24 69 71 77 51
21 15 58 48 71 31
65 86 36 26 46 93
97 64 27 49 16 58
29 5
23 30 83 49 59
20 43 93 75 61
33 72 97 74 13
46 26 43 75 38
82 30 76 15 88
15 82 46 11 77
59 98 62 58 52
27 76 65 23 73
51 29 83 59 15
81 72 41 32 58
66 10 37 98 49
72 71 43 59 18
19 60 68 95 50
70 26 84 56 45
81 37 45 56 42
82 96 96 49 71
81 94 78 69 69
78 15 55 87 89
19 35 43 37 42
46 98 22 12 99
99 30 90 60 18
44 56 16 94 95
59 57 25 64 74
99 18 85 77 35
38 99 83 58 25
86 52 41 60 63
50 35 60 10 25
18 69 45 14 86
50 12 58 94 10
27 2
39 26
63 17
64 46
75 13
26 25
21 45
15 22
41 41
98 92
27 81
37 65
39 25
53 50
72 55
12 42
66 65
10 96
90 90
93 77
24 70
64 49
87 79
33 99
59 11
49 43
43 31
76 85
27 5
35 20 10 91 64
77 51 94 40 72
81 32 58 39 36
18 95 49 79 77
87 62 61 95 85
48 87 56 64 47
53 98 32 20 24
39 47 95 59 33
40 30 95 90 68
69 81 90 39 95
43 75 56 19 23
27 24 99 86 80
10 20 29 84 57
57 98 98 99 18
48 17 94 66 20
85 34 47 41 20
66 40 15 59 71
83 40 25 40 36
58 88 96 74 98
94 85 65 50 54
93 79 43 62 17
42 82 38 57 76
53 17 73 98 12
40 92 48 86 61
18 21 89 73 39
72 72 39 96 33
31 58 51 90 65
16 1
36
58
18
15
37
70
72
25
88
52
73
39
26
38
56
17
9 9
80 94 76 27 45 67 60 87 46
94 87 22 65 51 72 58 41 68
86 30 13 64 45 41 66 37 63
32 50 94 82 93 80 43 95 32
11 27 16 86 92 39 36 12 17
87 14 10 46 88 79 21 61 51
37 74 41 71 41 96 46 95 81
94 88 28 81 46 49 26 65 45
83 72 37 95 26 84 56 94 35
AC output:

Code: Select all

6
10 4 19 9 2 5
3
1 2 3
25
2 15 9 8 17 22 4 13 16 19 1 29 26 21 7 6 3 12 24 23 25 5 28 10 20
4
17 14 20 1
3
13 12 8
5
19 4 15 26 17
11
7 5 1 8 25 13 16 27 22 18 9
4
11 22 24 5
16
4 16 3 8 13 1 5 14 12 10 15 2 6 7 11 9
2
3 1
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”