Contest 3 - Hints to Problems [OFFICIAL]

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 :slightly_smiling_face:

@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.

thanks @sidhant007

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 :smiley:

Happy Coding :wink: :smiley:

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 :smiley:
Happy Coding :wink:

1 Like

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

}

savekonoha
i am getting TLE
pls help
@sidhant007

please help me @sidhant007 :pleading_face::pleading_face:
EXUNC Questionā€¦

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

Koi help karsakta hai pleaseā€¦???

@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;

}

Here i found good explanation for DPAIRS.