Actually when you use multiset.erase(some_value) all instances of this value are removed from the multiset.
For example, if your multiset contains {1,2,4,4,4,5} and you say multiset.erase(4), your new multiset would be {1,2,5}
If you want to remove only one copy of an element, pass an iterator into the erase function.
Can someone help me in finding error in my code ? Its giving correct output for given test cases.
#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<unordered_map>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
map<string,string> rel;
for(int i=0;i<n;i++) {
string chef,country;
cin>>chef>>country;
rel[chef]=country;
}
map<string,int> chef;
map<string,int> country;
int maximum_chef_score=0;
string chef_name;
int maximum_country_score=0;
string country_name;
for(int i=0;i<m;i++) {
string s;
cin>>s;
chef[s]++;
country[rel[s]]=country[rel[s]]+chef[s];
if(chef[s]>maximum_chef_score) {
maximum_chef_score=chef[s];
chef_name=s;
}
else if(chef[s]==maximum_chef_score) {
if(chef_name>s) {
chef_name=s;
}
}
if(country[rel[s]]>maximum_country_score) {
maximum_country_score=country[rel[s]];
country_name=rel[s];
}
if(country[rel[s]]==maximum_country_score) {
if(country_name>rel[s]) {
country_name=rel[s];
}
}
}
cout<<country_name<<endl;
cout<<chef_name;
}
//found my mistake
@sidhant007 @sapient @ankurkayal @maverick16
For solving SUBPRNJL using PBDS , as given in hint 2, for each subarray that we are forming from the array , are we inserting all its elements into the PBDS first?
If we do this then , since each insertion operation is O(log\,n) , then isnt this PBDS formation O(n\,logn) ?
Then the overall algorithm would become O(n^{3}logn) , since O(n^2) for generating all the subarrays.
Wont that exceed the time limits?
Where is my understanding faulty? Any help is appreciated.
It(Chef of the year) can easily be done using two unordered maps, one for country and the other one for chefs. Sort them first by frequency and lexicograhically if two elements have the same freq
auto maxch = max_element(ch.begin(),ch.end(),[] (const pair<string,int> &p1, const pair<string,int> &p2) {
if(p1.se!=p2.se) return p1.se < p2.se;
else return (string(p1.fi)>p2.fi);
});
thanks.
@sidhant007 canāt there be a problem with the approach for DPAIRS with this as input:
3 2
10 10 100
4 3
Clearly there exists an answer with
10+4, 10+3, 100+4,100+3
But with the approach mentioned, we get
10+3, 10+4, 10+4, 100+4
which is the wrong answer as 10+4
is repeated
Tried SAVKONO using multisets!
#include <bits/stdc++.h>
using namespace std;
#define endl ā\nā
#define int long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
void solve(vector &arr, int n, int z)
{
multiset s;
for(auto x : arr) s.insert(x);
int ans = 0;
while(z>0 and !s.empty())
{
int power = *s.rbegin();
z -= power;
s.erase(s.find(power));
if((power/2) > 0) s.insert(power>>1);
ans++;
}
if(z<=0) cout << ans << endl;
else cout << āEvacuateā << endl;
return;
}
int32_t main()
{
fast;
int t; cin >> t;
while(tā)
{
int n,z; cin >> n >> z;
vector arr(n);
for(int i=0; i<n; i++) cin >> arr[i];
solve(arr,n,z);
}
return 0;
}
The Solved Time Discussion of Save Konoha Problem
Best : 0.03 Sec using Array with greedy approach
Solution : CodeChef: Practical coding for everyone
Better:0.04 and 0.05 sec using priority_queue
Solution1 : CodeChef: Practical coding for everyone (0.04 sec using ++cnt)
Solution2 : CodeChef: Practical coding for everyone (0.05 sec using cnt++)
good(worse I think :p) : 0.21 sec using multiset
solution : CodeChef: Practical coding for everyone
Another implementation hints using of set & pair has been given by Sidhant007 Sir. Implement this by yourself
Happy Coding
Time taken Analysis of Chef Of The Year
Best Approach is unordered_map
unordered_map solution : CodeChef: Practical coding for everyone (0.03 sec)
map solution : CodeChef: Practical coding for everyone (0.11sec)
unordered_map a little bit fast than map
Happy Coding
The PBDS formation isnāt exactly O(nlogn). Suppose you have the PBDS for subarray a[1,2,3,4,5,6], then to obtain the PBDS for subarray a[1,2,3,4,5,6,7] you just need to insert a[7]. So instead of O(nlogn) for each subarray, a simple O(1) transition works fine for some.
So if you consider subarrays starting at a particular index you will have n distinct starting positions and almost n subarrays for each starting position. In O(nlogn) you can make the PBDS for all these n subarrays for a particular starting position. hence the complexity O(n* nlogn)
Can someone please tell me why its giving tleā¦???
thanks alotā¦!!
EXUNC Questionā¦!!
#define lli long long int
#include
using namespace std;
#include<bits/stdc++.h>
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli n,q;
cin>>n>>q;
lli ar[n+1];
ar[0]=1e18;
for(lli i=1;i<=n;i++)
cin>>ar[i];
set<lli> s;
for(lli i=n;i>0;i--)
{
if(ar[i]%ar[i-1]==0);
else
s.insert(i);
}
while(q--)
{
lli a;cin>>a;
if(a==1)
{
lli i,x;
cin>>i>>x;
ar[i]=x;
if(ar[i+1]%ar[i]==0 && ar[i]%ar[i-1]==0)
{
s.erase(i);
s.erase(i+1);
}
else if(ar[i]%ar[i-1]==0)
{
s.erase(i);
s.insert(i+1);
}
else if(ar[i+1]%ar[i]==0)
{
s.insert(i);
s.erase(i+1);
}
else
{
s.insert(i);
s.insert(i+1);
}
}
else
{
lli i;cin>>i;
auto it=upper_bound(s.begin(),s.end(),i);
it--;
cout<<*it<<endl;
}
}
}
@sidhant007 its giving TLE error in case of the set. But fine with a priority queue. Thanks for your contribution.
EXUNC is such a nice problem. I would never have solved it with SET, I would have solved it with array. Thanks for sharing!
Yet Again a Subarray Problem - SUBPRNJL
For SUBPRNJL, check out merge sort segment tree implementation. Sucha great chance to improve your seg-tree understanding.
Here is a link to Merge Sort Tree
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
// cout<<āGfG!ā;
ll n ,m;
cin>>n>>m;
ll a[n],b[m];
map <ll,ll> a1,b1;
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
for(ll i=0;i<m;i++)
{
cin>>b[i];
}
for(ll i=0;i<n;i++)
{
a1.insert(pair<ll,ll>(a[i],i));
}
for(ll i=0;i<m;i++)
{
b1.insert(pair<ll,ll>(b[i],i));
}
ll cnt=m+n-1;
ll cn=0;
for(auto it=a1.begin();it!=a1.end();it++)
{
for(auto jt=b1.begin();jt!=b1.end();jt++)
{
if(cn == cnt)
{
break;
}
//cout<<" M="<<M<<"N="<<N<<" ";
// cout<<"cn="<<cn;
cout<<it->second<<" "<<jt->second<<"\n";
cn++;
}
}
return 0;
}