@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.
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 I add 3+1, 4,4,4?
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:
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
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
i don’t know about that.
i skipped to next question during contest
you can report to @admin about this issue
Thank you so much! That missed endl got me stuck for so long… lol, anyway TYSM!!!
Hey yeah, thank you for your helping hand. I missed and endl …lol which was the reason behind me getting WA everytime. Tysm!
Please check anyone why this code is not working
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n; cin>>n;
vector<int> arr(n);
vector<int> con(101, 0);
int ans = 0;
int pairs = 0;
for(int i = 0; i<n; i++){
cin>>arr[i];
con[arr[i]]++;
}
if(n == 1)
cout<<3<<endl;
else if(n == 2)
cout<<2<<endl;
else if(n>2){
for(int i = 0; i<101; i++){
if(con[i]%2){
con[i]+=1;
ans++;
}
if(con[i] != 0)
pairs++;
}
if(pairs == 1)
cout<<ans<<endl;
else if(pairs%2 == 0 && pairs>1)
cout<<ans<<endl;
else
cout<<ans+2<<endl;
}
}
int main(){
int t; cin>>t;
while(t--){
solve();
}
return 0;
}
thanks bhai:heartpulse:
i forgot about this case
Hey @saiyan_god 
,
your code is half correct but while(sticks>0) part has logic error also you don’t need to do this much till part where you counted extra for every odd count of number then just think that every even pair will contribute towards two side of rectangle so all you need after calculating extra is just check (size of array + extra ) is divisible by 4 or not this sum will always be even because for every number that counted odd has now a new number with which it became even so whole (size of array + extra) is even now.
We just need to check if((size of array + extra)%4==0 ) if not and we know this will be even that means remainder has 2 so we add 2 and we got our answer.
Here is my code.
#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n";
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
static char buffer[64];
int index = 0;
__uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
if (value < 0)
os << '-';
else if (T == 0)
return os << '0';
for (; T > 0; ++index) {
buffer[index] = static_cast<char>('0' + (T % 10));
T /= 10;
}
while (index > 0)
os << buffer[--index];
return os;
}
istream& operator >> (istream& is, __int128& T) {
static char buffer[64];
is >> buffer;
size_t len = strlen(buffer), index = 0;
T = 0; int mul = 1;
if (buffer[index] == '-')
++index, mul *= -1;
for (; index < len; ++index)
T = T * 10 + static_cast<int>(buffer[index] - '0');
T *= mul;
return is;
}
#endif
int add(long long a, long long b) {return ((a % MOD) + (b % MOD)) % MOD;}
int subtract(long long a, long long b) {return ((a % MOD) - (b % MOD)) % MOD;}
int mult(long long a, long long b) {return ((a % MOD) * (b % MOD)) % MOD;}
int add1(long long a, long long b) {return ((a % MOD1) + (b % MOD1)) % MOD1;}
int subtract1(long long a, long long b) {return ((a % MOD1) - (b % MOD1)) % MOD1;}
int mult1(long long a, long long b) {return ((a % MOD1) * (b % MOD1)) % MOD1;}
int expo(int a, int b, int mod) {
int res = 1;
while (b > 0)
{ if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;
} return res;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int mminvprime(int a, int b) {
return expo(a, b, b + 2);
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map<int, int> m;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
m[x]++;
}
int count = 0;
for (auto x : m)
{
if (x.second % 2)
{
count++;
}
}
int sum = n + count;
if (sum % 4 != 0) sum += sum % 4;
//since we need count of new elements added we subtracted total - original elements
cout << sum - n << "\n";
}
return 0;
}
1 Like