what is wrong in this
#include<bits/stdc++.h>
using namespace std;
int main()
{
priority_queue pq;
//int n,t,p_pow;
int t;
long long z;
cin>>t;
while(t–)
{ int count=0;
int n,p_pow;
cin>> n >>z;
for(int i=0;i<n;i++)
{
cin>>p_pow;
pq.push(p_pow);
}
while(pq.top()>0&&z>0)
{
z-=pq.top();
pq.push(floor(pq.top()/2));
pq.pop();
count++;
}
if(z>0)
cout<<“Evacuate”<<endl;
else
cout<<count<<endl;
}
return 0;
}
Hey @sidhant007, I’m getting WA for CVOTE(Chef of the Year) problem. I’ve applied the same logic as stated in the hints. Can you please tell what is wrong with my code…?
Can you also suggest another way to find the lexicographically smallest country and chef in this problem…?
Thanks in advance…!
but how u can be so sure that the sums founded previously would not be equal to the next calculated sums
I know the case which you are talking about, where if A_{1}, A_{2}, A_{3}, \cdots, A_{n} has duplicate elements and B_{1}, B_{2}, B_{3}, \cdots, B_{n} also.
In the problem there is a statement written which says :
“It is guaranteed that under the given constraints, a solution always exists.”
For the solution to exist both the sequences must have distinct elements and hence I am sure that the test cases on which the program is going to be judged will have distinct elements sequence.
@sidhant007 referring to Hint 2 of Yet Again a subarray Problem. How the ⌈K/m⌉th smallest element in S is same as Kth smallest in B?
Please do clear out my doubt.
problem Save Kanoba
In second line of while loop, it is giving error.
S.erase(S.rbegin())
but S.erase(–S.end()) is working fine.
Can you plz tell the reason?
I read the approach for CodeChef: Practical coding for everyone and implemented it using the PBDS ordered set.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree< pair<int,int> , null_type, less<pair<int,int > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define fs first
#define sc second
#define nl '\n'
#define set0(a) memset(a,0,sizeof(a))
#define REP(i,n) for (int i = 0; i < n; i++)
int arr[2002],mp[2002];
ordered_set s;
void solve()
{
int n,k;
scanf("%d%d",&n,&k);
REP(i,n)
scanf("%d",&arr[i]);
int ans=0;
REP(i,n)
{
set0(mp);
s.clear();
for(int j=i;j<n;j++)
{
s.insert({arr[j],j});
mp[arr[j]]++;
int len=j-i+1;
int m=(k+len-1)/len;
int p=(k+m-1)/m;
p--;
auto it=s.find_by_order(p);
int x=it->fs;
x=mp[x];
if(mp[x])
ans++;
}
}
printf("%d\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
solve();
}
however, this is the result I get
Is there a better implementation or should I ditch this approach altogether?
Can anyone tell what is wrong in this approach for Dpairs. It’s giving WA on some test cases
Here is my code…https://www.codechef.com/viewsolution/33132143
Need your help in Chef of the Year(CVOTE) problem. I have done question using unordered map and priority queue. I am getting correct answer when verified all the 3 examples (inputs) given in the problem statement. But i am not able to get correct answer when submitted here.
Can someone please help.
Link to the solution -
https://www.codechef.com/viewsolution/33157862
Hey @nisarg_140600. You’re not actually mapping the chef names to countries, rather you’re only mapping the count of names and countries.
Try dry running your code, and try to print the contents of the maps WordFreq and WordFrequency. You’ll find out your mistake…
s.end() points to the imaginary element which will exist next to the last element
thanks to all the volunteers , you guys are doing a fantastic job.
I have solved SAVKONO using the priority queue approach, is this code efficient? and i cant seem to figure out its time complexity any help?
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t ;
cin >> t ;
while(t–)
{
int n , z , cnt = 0;
cin >> n >> z ;
priority_queue q ;
while(n–)
{
int a ;
cin >> a ;
q.push(a);
}
while(z > 0)
{ if(q.top() == 0)
break;
z -= q.top();
int i = q.top();
q.pop();
q.push(i/2);
++cnt;
}
if(z > 0)
cout << “Evacuate” << endl;
else
cout << cnt << endl;
}
}
My code is failing the TC’s…Can anyone help…
Here is the code :-
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,z,p;
cin>>t;
while(t–)
{
cin>>n>>z;
priority_queue q;
for(int i=0;i<n;i++)
{
cin>>p;
q.push§;
}
int ans=0;
while(z>0 and q.top()>0)
{
int power=q.top();
q.pop();
z-=power;
ans++;
q.push(power/2);
}
if(ans>0)
cout<<ans<<"\n";
else
cout<<“Evacuate\n”;
}
return 0;
}
s.end() doesn’t points to the last element, it points to an imaginary end after the last element. You should use s.rbegin() for accessing last element, and similarly here in reverse iteration, s.rend() doesn’t points to the first element.
You have not defined the dtype for priority_queue which would be here.
Hey Can anyone help me in finding what am i doing wrong in the problem Save Konoha, As there can be same elements so instead of using Set i am using “multiset” still the solution is not accepted. I am pasting my solution here below. Please someone review it and let me know what i am doing wrong.
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
long long t;
cin>>t;
while(t--)
{
long long n,z,i,temp;
cin>>n>>z;
multiset<long long> s;
for(i=0;i<n;i++)
{
cin>>temp;
s.insert(temp);
}
long long count=0;
while(z>0 && !s.empty())
{
auto it=s.end();
it--;
long long ded= (*it);
z=z-ded;
count++;
s.erase(ded);
if(ded/2!=0)
s.insert(ded/2);
}
if(z>0)
{
cout<<"Evacuate"<<endl;
}
else
{
cout<<count<<endl;
}
}
}
why is this code giving me a wrong answer? CVOTE problem.
#include <bits/stdc++.h>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
map<string,string> country;
map<string,int> chef;
map<string,int> c;
for(int i=0;i<n;i++){
string name;
string cc;
cin>>name>>cc;
country[name]=cc;
chef[name]=0;
chef[cc]=0;
}
for(int i=0;i<m;i++){
string name;
cin>>name;
chef[name]++;
c[country[name]]++;
}
map<string,int>::iterator it;
it=c.end();
it–;
int temp=it->second;
while(it->second==temp && it!=c.begin()) it–;
if(it->second<temp) it++;
cout<first<<endl;
it=chef.end();
it–;
temp=it->second;
while(it->second==temp && it!=chef.begin()) it–;
if(it->second<temp) it++;
cout<first;
}
will be glad if anyone can help!
@sidhant007
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