Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

sowdeesnuts's blog

Duals (easy version) solution exceeding memory limit
By sowdeesnuts, history, 3 hours ago, In English 
void solve()
{
	int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int op=0; vector<pair<int,int>>ans;
    while(op<=50){
        vector<int>v1(arr.begin(),arr.end());
        sort(v1.begin(),v1.end());
        int mxele= v1[v1.size()-1];
        int mxelei= max_element(arr.begin(),arr.end())-arr.begin();
        int breakpnt=-1;
        for(int i=1;i<n;i++){
            if(arr[i]<arr[i-1]){
                breakpnt=i; break;
            }
        }
        if(breakpnt==-1) break;
        int req= (arr[breakpnt-1]-arr[breakpnt])/mxele ;
        arr[breakpnt]= arr[breakpnt]+ req*mxele;
        op= op+req;
        while(req--){
            ans.push_back({breakpnt,mxelei});
        }
        if(arr[breakpnt]<arr[breakpnt-1]){
            int extra=arr[breakpnt-1]-arr[breakpnt];
            //cout<<*lower_bound(v1.begin(),v1.end(),extra)<<endl;
            op++;
            int x=*lower_bound(v1.begin(),v1.end(),extra);
            for(int i=0;i<n;i++){
                if(arr[i]==x){
                    ans.push_back({breakpnt,i}); break;
                }
            }
            arr[breakpnt]= arr[breakpnt]+ *lower_bound(v1.begin(),v1.end(),extra);
            //cout<<arr[breakpnt]<<endl;
        }
        if(is_sorted(arr.begin(),arr.end())) break;
     }
    // if(is_sorted(arr.begin(),arr.end())){cout<<"yes"<<endl;}
    // else cout<<"NO"<<endl;
    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it.first+1<<" "<<it.second+1<<endl;
    }
}

The above approach is giving MLE on test case 2 and i cant understand why. Please help

Problem link: https://mirror.codeforces.com/problemset/problem/1854/A1

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sowdeesnuts (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sowdeesnuts (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Idk if it's the problem, but this seems strange:

int req= (arr[breakpnt-1]-arr[breakpnt])/mxele;

what if mxele is 0 or smth

then you use this req to push elements into array, maybe this req becomes really big at some point idk

→ Reply
»
11 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

When mxele is negative, req= (arr[breakpnt-1]-arr[breakpnt])/mxele ; can make req negative. When that's the case, the while(req--) loop never reaches zero (because req is negative, and stays negative), and thus never terminates. You're pushing an element to the end of a vector inside the loop, and so the vector becomes arbitrarily large and consumes all the memory.

By the way, mxele being 0 would result in a division by zero, so that needs to be fixed as well.

→ Reply