NullPhase's blog

By NullPhase, history, 8 months ago, In Russian

Hello Codeforces,

I participated in a contest yesterday (not on CF) and ran into a weird issue that left me pretty confused. I'm hoping someone can explain the "under the hood" reason for this.

The Problem

I was working on a problem where I had to sum up "danger" values for certain "suspects." Initially, I used a range-based for loop. This version only gave me a Partial Solution (a TLE on larger test cases)(and yes I know my code is pretty terrible):

    int n; 
    cin >> n; 
    vector<pair<st,int>> danger(n); 

    for(auto &it:danger) cin >> it.first >> it.second; 

    int m; 
    cin >> m; 
    vector sus(m); 

    for(auto &it : sus) cin >> it; 

    int cnt = 0; 
    for(auto it: sus){ 
        for(auto i : danger){ 
            if(it == i.first)cnt += i.second; 
        } 
     } 

     cout << cnt << endl;

The "Fix"

After some debugging, I decided to change my range-based loops to index-based. Out of curiosity and absence of hope I submitted it, and... it got accepted

Here is the code:

    int n;
    cin >> n;
    vector<pair<st,int>> danger(n);

    for(int i = 0; i < n; i++) cin >> danger[i].first >> danger[i].second;

    int m;
    cin >> m;
    vector<st> sus(m);

    for(int i = 0; i < m; i++) cin >> sus[i];

    int cnt = 0;
    for(int i = 0; i < m; i++){
        for(int j =0 ; j < n; j++){
            if(sus[i] == danger[j].first)cnt += danger[j].second;
        }
    }

    cout << cnt << endl;

Can someone please explain to me, why? Because my teacher said they work with same speed and I should use whatever I wanted to use.

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

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Assuming st is define for string. Problem is that, while index-based and iterator-based loops are equivalent, range based are not. for (auto x : some_container) copies all elements one by one (on each iteration). For trivial and light objects it is okay, for heavy containers it is better to use auto&. Here I guess they are asymptotically equivalent, but your range-based loop works longer (have bigger constant). But in general it can make O(n^2) solution from O(n) silently.

  • »
    »
    8 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Noted, thank you, I didnt know such inside structure of c++, now I understand why I see auto &it in solution of high hating coders, thank you!