Re: 103 problem ...
Posted: Mon Oct 01, 2012 9:30 pm
Look up the Longest Increasing Subsequence algorithm.
Page 13 of 14
Re: 103 problem ...
Posted: 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.
Re: 103 problem ...
Posted: Mon Oct 22, 2012 9:24 pm
The judge could have been down, try resubmitting.
help about WA on #103
Posted: 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();
}
}
}
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();
}
}
}
Re: help about WA on #103
Posted: 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).
Re: help about WA on #103
Posted: Mon Nov 19, 2012 7:41 am
i have fix this issue.
Re: help about WA on #103
Posted: 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
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
Re: help about WA on #103
Posted: 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();
}
}
}
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();
}
}
}
103 longest inc seq question
Posted: 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 = ?
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 = ?
Re: 103 longest inc seq question
Posted: Tue Dec 18, 2012 12:12 am
Re: 103 longest inc seq question
Posted: Tue Dec 18, 2012 1:18 am
I had no idea this existed 
WA on problem 103
Posted: 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:
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.
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 20Code: 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;
}Re: WA on problem 103
Posted: Mon Jun 24, 2013 11:55 pm
Print a newline at the end of the last line.
Re: WA on problem 103
Posted: Tue Jun 25, 2013 12:03 am
K, I stopped suppressing the newline at the end of the output, but still got WA.
Re: WA on problem 103
Posted: Wed Jun 26, 2013 12:59 am
Input:AC output:
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
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