 # STICKS - Editorial

Tester: Misha Chorniy
Editorialist: Pushkar Mishra

Simple

Greedy

### PROBLEM:

Given an array of A of N integers which represent stick lengths, we have to report the maximal area over all the rectangles that we can form with the given sticks without breaking any.

### EXPLANATION:

The problem is a simple one based on a very basic property of all rectangles: the opposite sides of a rectangle are parallel, and hence, equal in length. The area of a rectangle is given by base B multiplied by height H. Now, to maximise the area, we simply need to maximise the length of sticks we choose as our B and H. This is pretty intuitive but we can also invoke the exchange argument method (page 3 of link) to give a more formal argument as proof of why this works (left to reader as a simple learning exercise).

Now we come to the implementation detail of the above mentioned algorithm. Note that N and A_{max} both range between 1 and 10^3. So, one way is that we simply keep an array Count of length 10^3 wherein Count[i] is the number of sticks of length i that we have. Once we have populated this structure, we can simply scan from 10^3 down to 1. If while scanning, we can find one field which has more than 3 sticks, then that i can be our height and base both; at this point we terminate our scan. If we find a field that has more than 1 stick, we can make it either our height or base and continue our scan to find a value for the other one. If at the end of scan we don’t find at least two i for which the count is more than 1, then we output -1 since no rectangle can be formed.

The other implementation can be by using a map instead of an array. In that case, if the N is much smaller than A_{max}, we can get a better performance. Both of the implementations easily pass for the given constraints.

Please see editorialist’s/setter’s program for implementation details.

### COMPLEXITY:

\mathcal{O}(N\log N) or \mathcal{O}(A_{max}) per test case.

### SAMPLE SOLUTIONS:

1 Like

whats wrong with my implementation ? link-
https://www.codechef.com/viewsolution/10624567

I implemented in c++ and java. In c++ I am getting run-time error when I am running the code in the code-compile-run here. And in Java it’s wrong answer.

Java Implementation:

http://pastebin.com/gAFVG2Fs

C++ Implementation:

http://pastebin.com/nf4zuNSM

If possible please tell me what is wrong with these two codes.

A different implementation of the above logic.

https://www.codechef.com/viewsolution/10616757

First enter all the length of the sticks in an array, sort it in O(nlogn) and then traverse the array from the right end, checking for multiple instances of any stick. This also covers the special case of a square.

hey,can anyone just help me to find error in my code…
https://www.codechef.com/viewsolution/10623972

Try this test:
1
4
1 2 3 3
Your solution output 0, but must be -1

BTW, change for(i=0;i<10002;i++) to for(i=0;i<10001;i++), your arrays size only 10001

1

4

1 1 1 1

Your solution output -1, but must be 1.

You forget about square case too

can u elaborate more ,which case i have omitted

1

4

1 1 1 1

ok,I got it …thank U

A different approach,which has O(N*logN) time complexity but uses Only One Array is as follows:

After storing the array containing the lengths of sticks, sort it.
We must note that the same lengths will automatically come together after sorting.
For example,

the array 5 2 8 3 1 2 4 3 5

becomes 1 2 2 3 3 4 5 5 8

Then if we traverse the array from backwards picking up the first two occurrences of a pair of same numbers(for e.g (5,5) would be the first occurrence and (3,3) would be the second in this case.Don’t forget to break the loop here. )
the answer would be 5*3=15.If we are unable to find two occurrences we print -1.

The JAVA solution of the problem using this method is:

@code_blooded_ I did same in C++.
https://www.codechef.com/viewsolution/10622129

1 Like

https://www.codechef.com/viewsolution/10618548 Please let me know what is wrong with this solution.

@sreedishps if N<3 , then you are not reading sticks length

https://www.codechef.com/viewsolution/10627623 Hey, Can anybody tell why I am getting WA ? I used the algorithm mentioned in editorial.

1

8

1 1 2 2 2 2 3 3

Answer is 6 = 2 * 3, but your output will be 2 * 2 = 4

@mgch Thanks https://www.codechef.com/viewsolution/10621785 Can somebody please look into it,I am getting a WA.

Can anybody tell why I am getting WA ? link-https://www.codechef.com/viewsolution/10630873

//