Fail: Passing by Reference is Actually Evil

#	User	Rating
1	tourist	3985
2	jiangly	3885
3	jqdai0815	3682
4	Benq	3580
5	orzdevinwang	3526
6	ksun48	3506
7	ecnerwala	3505
8	Radewoosh	3457
9	Kevin114514	3377
10	gamegame	3374

#	User	Contrib.
1	cry	170
2	Um_nik	162
3	atcoder_official	161
4	maomao90	159
5	-is-this-fft-	158
6	djm03178	157
7	Dominater069	156
8	adamant	154
9	luogu_official	153
10	awoo	152

Good evening, Codeforces community!

Let me introduce a useful pattern that appears in many algorithms and source codes.

Why you should pass collections by reference in C++

Take a look at this code:

Code

bool visited[200005];

void dfs(vector<vector<int>> g, int n, int m, int node)
{
    if (visited[node]) return;
    visited[node]=true;
    for (auto nxt : g[node]) dfs(g,n,m,nxt);
}

It is a DFS implementation. Graph $$$g$$$ is given that has $$$n$$$ nodes and $$$m$$$ edges. Can you guess the time complexity?

Time Complexity

But why?

Here is the correct code:

Code

bool visited[200005];

void dfs(vector<vector<int>> &g, int n, int m, int node)
{
    if (visited[node]) return;
    visited[node]=true;
    for (auto nxt : g[node]) dfs(g,n,m,nxt);
}

What is different?

When you shouldn't pass by reference

Today, I attempted 2053D - Refined Product Optimality during the official contest. Briefly, given two arrays $$$a_1,a_2,\ldots ,a_n$$$ and $$$b_1,b_2,\ldots, b_n$$$ and $$$q$$$ queries, one should find a greedy algorithm to answer the queries.

My first greedy idea was to sort both arrays and then $$$\min(a_1,b_1) \cdot \min(a_2,b_2) \cdot \ldots \cdot \min(a_n,b_n)$$$ is the answer. Before moving onto the main $$$\mathcal{O}((n+q)\log n)$$$ solution, I wanted to test my idea with brute force in $$$\mathcal{O}(nq \log n)$$$ time. I used the following code:

Code

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define xx first
#define yy second

using namespace std;
long long int typedef li;
pair<int,int> typedef pii;
const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

int calc(vector<int> &a, vector<int> &b, int n)
{
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    long long res=1;
    for (int i=0;i<n;i++) (res*=min(a[i],b[i]))%=mod;
    return res;
}

main()
{
    FAST;

    int t; cin>>t;
    while (t--)
    {
        int n,q; cin>>n>>q;
        vector<int> a(n),b(n);
        for (auto &it : a) cin>>it;
        for (auto &it : b) cin>>it;

        cout<<calc(a,b,n)<<" ";

        while (q--)
        {
            int o,x; cin>>o>>x; x--;
            if (o==1) a[x]++;
            if (o==2) b[x]++;
            cout<<calc(a,b,n)<<" ";
        }

        cout<<"\n";
    }
}

//Note to self: Check for overflow

Since I had Wrong Answer on the sample (test $$$1$$$), I moved on to the next greedy idea. It was more complicated and difficult to implement. At least I had a proof that it was correct. Unfortunately, after spending two hours of implementing it during the contest, I failed. The second idea was just too difficult for handling the queries. The problem was impossible, or at least too hard for the position, I thought.

Fun fact: The first idea was correct. Its $$$\mathcal{O}((n+q)\log n)$$$ implementation that handles queries is simple as well. So, why did it give Wrong Answer?

Really, why?

What should I have done instead?

The problem is not impossible. I just made a blunder.

Final tips

Passing local variables by reference is cool, but be careful when modifying them, as you might not like the result.
Copying is useful when you don't want to keep changes.
Reference is useful when you do want to keep changes globally and save some time and memory.
Don't overcomplicate things.
Learning from your own mistakes is good. Learning from somebody else's is better.
Glory to Arstotzka!