You are not logged in. Please login at www.codechef.com to post your questions!

×

STICKS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

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:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 25 Jun '16, 12:31

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156281
accept rate: 4%

edited 27 Jun '16, 00:14

admin's gravatar image

0★admin ♦♦
15.9k347484508


link

answered 27 Jun '16, 10:08

easy_'s gravatar image

2★easy_
1286
accept rate: 0%

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

link

answered 27 Jun '16, 00:15

mkfeuhrer's gravatar image

4★mkfeuhrer
213
accept rate: 0%

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

(27 Jun '16, 01:33) mgch7★

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.

link

answered 27 Jun '16, 00:28

priyabrata1992's gravatar image

2★priyabrata1992
1
accept rate: 0%

You forget about square: 1

4

1 1 1 1

Your solution output -1, but must be 1.

(27 Jun '16, 01:35) mgch7★

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.

link

answered 27 Jun '16, 00:32

utkarsh1997's gravatar image

5★utkarsh1997
5407
accept rate: 10%

edited 27 Jun '16, 11:28

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

link

answered 27 Jun '16, 00:58

nanhe's gravatar image

3★nanhe
413
accept rate: 0%

You forget about square case too

(27 Jun '16, 01:37) mgch7★

can u elaborate more ,which case i have omitted

(27 Jun '16, 01:53) nanhe3★

1

4

1 1 1 1

(27 Jun '16, 01:57) mgch7★

ok,I got it ..thank U

(27 Jun '16, 02:00) nanhe3★

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. :P ) 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:

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

link

answered 27 Jun '16, 02:50

code_blooded_'s gravatar image

4★code_blooded_
211
accept rate: 0%

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

link

answered 27 Jun '16, 10:46

sreedishps's gravatar image

4★sreedishps
1
accept rate: 0%

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

link

answered 27 Jun '16, 11:41

arunmittal53's gravatar image

4★arunmittal53
92
accept rate: 0%

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

link

answered 27 Jun '16, 12:13

chandan5's gravatar image

3★chandan5
11
accept rate: 0%

edited 27 Jun '16, 12:25

1

8

1 1 2 2 2 2 3 3

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

(27 Jun '16, 12:26) mgch7★

@mgch Thanks :)

(27 Jun '16, 14:50) chandan53★

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

link

answered 27 Jun '16, 15:59

pada1211's gravatar image

3★pada1211
1
accept rate: 0%

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

link

answered 27 Jun '16, 20:20

shivangnlucky's gravatar image

3★shivangnlucky
1
accept rate: 0%

Hi,

This is my code https://www.codechef.com/viewsolution/10630891

Can anyone please help me to tell why is this WA ?

Thanks

link

answered 27 Jun '16, 20:23

nits24's gravatar image

0★nits24
1
accept rate: 0%

y am i getting WA in this solution? https://www.codechef.com/viewsolution/10632476

link

answered 28 Jun '16, 00:45

mayank_4098's gravatar image

2★mayank_4098
1
accept rate: 0%

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

can someone help me with my code..? its coming as "time limit exceeded"..

link

answered 28 Jun '16, 09:21

sathiya_chakra's gravatar image

2★sathiya_chakra
1
accept rate: 0%

Can anyone help with the code. I have included the square case too. But I don't know why my solution is not getting accepted. https://www.codechef.com/viewsolution/10624628

link

answered 28 Jun '16, 11:18

sebastinsanty's gravatar image

2★sebastinsanty
1
accept rate: 0%

@pada1211 Your code fails for 1 4 1 2 3 3

link

answered 28 Jun '16, 19:17

rc1c2's gravatar image

2★rc1c2
454
accept rate: 22%

edited 28 Jun '16, 19:18

https://www.codechef.com/viewsolution/10621220 I cant seem to figure out whats wrong with my solution. It passes most of the test cases I can come up with. Please help out. Thanks in advance :) PS: I looked through some solutions.. They use the size of count array as 10000 whereas the mentioned size is 10^3 = 1000. Why is that so? I tried both ways by the way. Still wrong answer.

link

answered 29 Jun '16, 03:28

apheleia's gravatar image

2★apheleia
1
accept rate: 0%

@sreedishps This case gives Runtime error with your code : 1 7 4 4 3 3 3 3 1

link

answered 29 Jun '16, 17:16

yashkant's gravatar image

2★yashkant
1
accept rate: 0%

edited 29 Jun '16, 17:17

@sebastinsanty,

check the case

1

7

2 3 1 1 2 1 1

answer should be 2

link

answered 30 Jun '16, 13:22

code_blooded_'s gravatar image

4★code_blooded_
211
accept rate: 0%

https://www.codechef.com/viewsolution/10644839 Can someone explain why am i getting WA

link

answered 30 Jun '16, 16:08

manmeet_tarun's gravatar image

2★manmeet_tarun
1
accept rate: 0%

Can somebody please tell me at what test i got wrong answer https://www.codechef.com/viewsolution/10647330

link

answered 01 Jul '16, 00:29

sahil_master's gravatar image

2★sahil_master
1
accept rate: 0%

Please can anyone point out the error in my code- https://www.codechef.com/viewsolution/10793814

link

answered 11 Jul '16, 20:01

newbie20's gravatar image

2★newbie20
1
accept rate: 0%

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

I am getting the required output, but its saying wrong answer :(

link

answered 21 Jul '16, 13:04

pratik938's gravatar image

0★pratik938
1
accept rate: 0%

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

Java Code: I am getting wrong answer for this, while its running perfectly on local compiler.

Yes i have taken some extra boolean flags ..:P

link

answered 22 Jul '16, 00:06

pratik938's gravatar image

0★pratik938
1
accept rate: 0%

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

Java code: I am getting WA, but its running perfectly on my system.

ye I have taken few extra boolean flags :P

link

answered 22 Jul '16, 00:08

pratik938's gravatar image

0★pratik938
1
accept rate: 0%

As usual,although I have passed the given test cases,I cant seem to find the reason why my code is getting a WA!

Here's the link to the code:-

http://pastebin.com/NbKdECcb

link

answered 27 Jul '16, 00:18

arpanm96's gravatar image

1★arpanm96
1
accept rate: 0%

Please somebody help me, I am getting WA https://www.codechef.com/viewsolution/10935149

link

answered 29 Jul '16, 10:59

ssgg2's gravatar image

3★ssgg2
1
accept rate: 0%

Can anyone help me with my code https://www.codechef.com/viewsolution/11238582 . Getting wrong answer

link

answered 24 Aug '16, 00:34

keertika32's gravatar image

0★keertika32
111
accept rate: 0%

My Java implementation is giving me wrong answer although it's working on eclipse. https://www.codechef.com/viewsolution/11248379 Please help!

link
This answer is marked "community wiki".

answered 25 Aug '16, 23:29

aliasss's gravatar image

0★aliasss
1
accept rate: 0%

can anyone say me what is wrong with my output?? or which case did i miss https://www.codechef.com/viewsolution/13211673

link

answered 06 Apr, 17:32

mahiyuvi's gravatar image

0★mahiyuvi
1
accept rate: 0%

C code Can any one say me what is wrong with the code.. its working fine in code blocks..but am getting wrong answer warning while submitting. could anyone please explain?? here is the link https://www.codechef.com/submit/complete/13211715

link

answered 06 Apr, 17:46

mahiyuvi's gravatar image

0★mahiyuvi
1
accept rate: 0%

C code Can any one say me what is wrong with the code.. its working fine in code blocks..but am getting wrong answer warning while submitting. could anyone please explain?? here is the link https://www.codechef.com/submit/complete/13211715

link

answered 06 Apr, 17:46

mahiyuvi's gravatar image

0★mahiyuvi
1
accept rate: 0%

Iam getting WA.But it is working fine in code blocks https://www.codechef.com/viewsolution/13211715 could anyone explain pls

link

answered 06 Apr, 17:48

mahiyuvi's gravatar image

0★mahiyuvi
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×780
×716
×42
×7

question asked: 25 Jun '16, 12:31

question was seen: 5,760 times

last updated: 25 Jun, 21:09