 # RECSTI Editorial

Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin

Cakewalk

Basic Arithmetic

# PROBLEM:

You have a bundle of N sticks, the ith stick has a length Li meters. Find the minimum number of sticks you need to add to the bundle such that you can construct some rectangles and each stick of the bundle belongs to exactly one rectangle.

# EXPLANATION:

Think of the problem as a combination of 2 tasks:

1. Pairing every length Li with an equal length.
2. Ensuring that the total number of sticks after adding the requisite number to complete all the pairs is a multiple of 4.

A rectangle contains pairs of equal and opposite sides. So every length should be present even number of times. Once every length is paired, it has to be ensured that the total number of sides are a multiple of 4. This can be done by simply adding the required number of pairs.

# TIME COMPLEXITY:

The above solution required the program to iterate over the given array atleast once. Hence, the solution has a time complexity of O(N) where N is the size of the array.

# SOLUTION:

1 Like

this will be the scenerio:
adding one stick of length 4 will make a square (rectangle with all sides equal)
adding one stick of length 1 and 3 each will make another rectangle
it is still consistent with editorial

1 Like

@rajat082000
i also used maps, but i used unordered maps. either way it would not matter.

if you could show your code maybe something else is the problem.

can someone plz help me why my code is failing ?

``````int main() {

fastIO();
w(t){
int n;
cin>>n;

unordered_map<ll,ll> mp;
int x;
while(n--){
cin>>x;
mp[x]++;
}

ll sticks=0,extra=0;
vi square;
for(auto i=mp.begin();i !=mp.end();i++){
if(i->ss%2 != 0) {   //making it even and 2's divisor
i->ss = i->ss + 1;
extra++;
}
if(i->ss >=4) {//same side is 4 , we can get a square
i->ss = i->ss - 4;
square.pb(i->ff);
}
sticks+=i->ss;
}
for(int i:square){
if(mp[i]==0)
mp.erase(i);
}

while (sticks>0){
int stick1=0,stick2=0;
//find two non-zero sticks and pair them
auto i=mp.begin();
if(mp.size()>1){

//stick 1
i->ss=i->ss-2;
stick1=i->ff;
i++;
//stick 2
i->ss=i->ss-2;
stick2=i->ff;
sticks-=4;
if(mp[stick1] ==0)   mp.erase(stick1);
if(mp[stick2] ==0)   mp.erase(stick2);
}else{
extra+=i->ss;
sticks-=i->ss;
}
}
cout<<extra<<"\n";
}
return 0;
}
``````

can you provide all test case?

why everyone has added 2 if answer is not multiple of 4?

1 Like

https://www.codechef.com/viewsolution/61899265
in this submission you missed the “endl” in last line

I think you have this doubt
when the freq of any ele is odd we added the sticks to make them even
now total number of sticks will be even
if we make some rectangles
remaining sticks will be even
example:
n=4
1 2 3 3
(1 1 2 2 3 3)
total number of string is not multiple of 4

n=4
1 2 3 4
we added the sticks(1 2 3 4)
(1 1 2 2 3 3 4 4)
total number of sticks is multiple of 4

thanks got it

no you can’t do that
i also had this doubt initially
but then i read this line in the problem statement
`each side of a rectangle should be formed with exactly one stick.`

what if we have all the sticks of same length.
like we have 4 sticks of length 3 3 3 3 ;
the output according to the given solution is coming out to be zero, but it must be 4, since they we will be requiring 2 pair of sticks of different lengths

how is a rectangle formed with 2 2 2 2 2 2 ??
the correct ans should be 6 whereas it’s showing 2.!

they will form a square which is a rectangle with all equal sides

7
1 1 1 1 1 2 2
why answer for this TC is 1?
its answer should be (1,1,2,2) (1,1,3,3) (1,1,4,4) → 5(1,3,3,4,4)??

That line was added in middle of the contest and there was not any announcement of that