Pi-nan's blog

By Pi-nan, history, 18 months ago, In English

can anyone explain to me how to solve this problem Ceil and Duel using min-cost max flow?

my approach was to build a flow network i.e. if node i have atk value >= node j ceil value then there will be an edge from j to i with capacity 1 and cost (atk[i]-ceil[j]), similarly if node i has def value > node j ceil value then there will be edge from j to i with capacity 1 and cost 0, and then connect all ceil's node to super source i.e. superSource -> ceil, and connect all atk and def node to super sink i.e. atk/def -> superSink with capacity 1 and cost 0. after building this network we will find min_cost_max_flow and after this, if all atk/def nodes are visited then we will add ceil[i] such that ceil's ith node is not used. I don't know why this is failing on test 28.

Link to my submission

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Pi-nan, history, 3 years ago, In English

I am getting below run time error in Codeforces, though code works as expected in my local compiler. Time: 0 ms, memory: 0 KB Verdict: RUNTIME_ERROR I submitted my code for http://codeforces.com/contest/962/problem/D

Code is below.

include<bits/stdc++.h>

using namespace std;

int main() {

int n;
cin >> n;
vector<int>a(n);
map<int,set<int>>m;
for(int i=0;i<n;i++)
{
    cin >> a[i];
    m[a[i]].insert(i);
}
map<int,set<int>>::iterator it;
int flag=1;
while(flag)
{
    flag=0;
    for(it=m.begin();it!=m.end();it++)
       if(it->second.size()>=2)
       {
         flag=1;
         break;
       }
    if(flag==0)
       break;
    set<int>:: iterator it1;
    set<int>s1;
    s1=it->second;
    it1 = s1.begin();
    int val = it->first;
    int gh = *it1;
    s1.erase(it1);
    it1++;
    int kl = *it1;
    s1.erase(it1);
    if(s1.size()==0)
       m.erase(val);
    else
       it->second=s1;
    val*=2;
    m[val].insert(kl);
}
vector<int>ans(n,-1);
int cnt=0;
for(it=m.begin();it!=m.end();it++)
{
    set<int>::iterator it1;
    set<int>s2;
    s2=it->second;
    it1=s2.begin();
    int val = it->first;
    for(it1=s2.begin();it1!=s2.end();it1++)
    {
       ans[*it1]=val;
       cnt++;
    }
}
cout << cnt << "\n";
for(int i=0;i<n;i++)
    if(ans[i]!=-1)
    cout << ans[i] << " ";
return 0;

}

Unable to understand the error. Please suggest how to solve it.

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it