Contest 3 - Hints to Problems [OFFICIAL]

arun8276 · June 7, 2020, 6:18am

Hello all,

For the FENCE problem, When using multimap, i am getting TLE for only N,M <= 1000, original constraints are ok. If i use set<pair<int,int>>, all subtasks are cleared. What is the difference?

#include <bits/stdc++.h>

using namespace std;

multimap<int,int> _points;
int n, m;

int _find_border(int p, int q)
{
int flag = 0;

if(p == 0 || q == 0)	return 1;
if(p > n || q > m)	return 1;

auto range = _points.equal_range(p);
for(auto itr=range.first; itr != range.second; itr++)
{
	if(itr->second == q)
	{
		flag = 1;
		break;
	}
}

if(!flag) return 1;
return 0;

}

int main(void)
{
int k, tc, r, c;
int total = 0;

cin>>tc;
while(tc--)
{
	cin>>n>>m>>k;
	for(int i=0; i<k; i++)
	{
		cin>>r>>c;
		_points.insert(make_pair(r, c));
	}

	for(auto itr=_points.begin(); itr != _points.end(); itr++)
	{
		//check top
		total += _find_border(itr->first-1, itr->second);
		//check down
		total += _find_border(itr->first+1, itr->second);
		//check left
		total += _find_border(itr->first, itr->second-1);
		//check right
		total += _find_border(itr->first, itr->second+1);

		//cout<<total<<endl;
	}

	cout<<total<<endl;
	total = 0;
	_points.clear();
}

return 0;

}
https://www.codechef.com/viewsolution/33881277
Could someone help to understand why multimap can’t be used?

Thanks a lot

soham1192k · June 7, 2020, 10:56am

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.

ismav12345 · June 10, 2020, 6:49am

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

thethinker01 · June 11, 2020, 4:26pm

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

neghat14 · June 13, 2020, 10:06am

thanks @sidhant007

waltzer47 · June 14, 2020, 7:51am

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

wickedknight · June 14, 2020, 11:03am

thanks.

yashsri421 · June 19, 2020, 2:26pm

@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

varun_man2810 · June 21, 2020, 2:38pm

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

one_piece4000 · June 22, 2020, 3:29am

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

one_piece4000 · June 22, 2020, 5:06am

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

maverick16 · June 23, 2020, 5:39am

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)

jais_sat · June 25, 2020, 10:17am

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

}

swapnil_14 · June 25, 2020, 5:14pm

savekonoha
i am getting TLE
pls help
@sidhant007

jais_sat · June 25, 2020, 5:40pm

please help me @sidhant007
EXUNC Question…

jais_sat · June 26, 2020, 7:48pm

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

Koi help karsakta hai please…???

ruhil_1993 · July 12, 2020, 11:03am

@sidhant007 its giving TLE error in case of the set. But fine with a priority queue. Thanks for your contribution.

dardev · July 17, 2020, 11:04am

EXUNC is such a nice problem. I would never have solved it with SET, I would have solved it with array. Thanks for sharing!

dardev · July 17, 2020, 1:09pm

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

hacktom123 · July 23, 2020, 7:59am

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

}