RECSTI Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin

DIFFICULTY:

Cakewalk

PREREQUISITES:

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:

Editorialist’s Solution
Setter’s Solution
Tester’s Solution

2

what about 1,3,4,4,4 ?

1 Like
4

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
so answer should be 3
it is still consistent with editorial

1 Like
6

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

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

7

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;
}
8

Can I add 3+1, 4,4,4?

9

can you provide all test case?

10

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

1 Like
11

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

12

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:
CASE 1: add2
n=4
1 2 3 3
(1 1 2 2 3 3)
total number of string is not multiple of 4
we add 2 here

CASE2: add0
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
we don’t add 2 here

13

thanks :slight_smile: got it

14

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.

15

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

16

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

17

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

18

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)??

19

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

21

i don’t know about that.
i skipped to next question during contest
you can report to @admin about this issue

22

Thank you so much! That missed endl got me stuck for so long… lol, anyway TYSM!!!

23

Hey yeah, thank you for your helping hand. I missed and endl …lol which was the reason behind me getting WA everytime. Tysm!