Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

yshen94's blog

By yshen94, history, 6 weeks ago, In English

For submission #287793085, I used dp and matrix to solve the problem. it seems that the memory limit is exceed. I know that a lot of people solve the problem using a map, but I am still curious whether using dp and matrix could be a successful solution with modifications in some way.

Full text and comments »

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

By yshen94, history, 6 weeks ago, In English

As a newbie, I am just trying to solve Codeforces Round 977 C1.

Initially, I was thinking about any effective data structure. Then I saw some solutions submitted like below, and I just find it really difficult to comprehend. What is the best way to understand what the solution is doing.

int t,n,m,q,a,to[200005],b;

int main(){

scanf("%d",&t);

while(t--){

    scanf("%d%d%d",&n,&m,&q);

    for(int i=1;i<=n;i++)scanf("%d",&a),to[a]=i;

    int ans=1,cur=0;

    for(int i=1;i<=m;i++)scanf("%d",&b),ans&=(to[b]<=cur+1),cur=max(cur,to[b]);

    puts(ans?"YA":"TIDAK");

}

}

Full text and comments »

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

By yshen94, 6 weeks ago, In English

really curious about the performance difference bewteen array and vector.

for 2023A — Concatenation of Arrays,

I passed the test using array as in #287237470 while failed the test using vector as in #287234748. The error shows "exit code: -1073741819 (STATUS_ACCESS_VIOLATION), checker exit code: 0, verdict: RUNTIME_ERROR"

maybe I am quite new in Codeforces. will be digging deeper into the performance difference.

Full text and comments »

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

By yshen94, history, 7 weeks ago, In English
  • Vote: I like it
  • -15
  • Vote: I do not like it

By yshen94, history, 7 weeks ago, In English

Keep a record on problems solved and to solve everyday

Leetcode

4 medium Leetcode problems

3191

2938

similar ones:

921 1963

670

1405

2044

3 hard ones

1691

3036

2014

Codeforces questions to solve (will be simply ignoring the first two problems as they tend to be easy) 2025 CDEFG

The bold ones are the ones to be solved

Full text and comments »

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

By yshen94, history, 2 months ago, In English
  • Vote: I like it
  • +1
  • Vote: I do not like it

By yshen94, history, 2 months ago, In English

The problem appears to be:

==> Downloading and installing Homebrew... fatal: unable to access 'https://github.com/Homebrew/brew/': Error in the HTTP2 framing layer Failed during: /usr/bin/git fetch --quiet --progress --force origin

How the problem is solved:

https://github.com/orgs/Homebrew/discussions/668

Full text and comments »

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

By yshen94, history, 5 months ago, In English

the difference between using a reference (&) and a regular member variable

Let me explain the difference between using a reference (&) and a regular member variable in this context, and why a regular member variable is preferred.

References in C++ In C++, a reference is an alias for another variable. When you declare a reference, it must be initialized to refer to an existing object, and it cannot be reassigned to refer to another object after initialization.

Using a Reference When you declare a member variable as a reference, you are essentially saying that this member variable will always refer to some other existing variable. Here is what it looks like in your context:

cpp Copy code class NumMatrix { public: vector<vector>& pre_sum;

NumMatrix(vector<vector<int>>& matrix) : pre_sum(matrix) {
    // Implementation
}

}; Here, pre_sum is a reference to matrix. This means pre_sum will always refer to matrix and cannot be reassigned to refer to something else. This is not suitable for your use case because you want pre_sum to be an independent data structure that holds the prefix sums, not just a reference to the input matrix.

Using a Regular Member Variable A regular member variable is an independent variable that is part of the object and can be initialized and modified as needed. Here is what it looks like in your context:

cpp Copy code class NumMatrix { public: vector<vector> pre_sum;

NumMatrix(vector<vector<int>>& matrix) {
    // Check if the input matrix is empty
    if (matrix.empty() || matrix[0].empty()) return;

    int m = matrix.size();
    int n = matrix[0].size();

    // Initialize pre_sum with the same dimensions as matrix
    pre_sum = vector<vector<int>>(m, vector<int>(n, 0));

    // Calculate prefix sums
    pre_sum[0][0] = matrix[0][0];
    for(int i = 1; i < m; ++i) {
        pre_sum[i][0] = pre_sum[i-1][0] + matrix[i][0];
    }
    for(int j = 1; j < n; ++j) {
        pre_sum[0][j] = pre_sum[0][j-1] + matrix[0][j];
    }
    for(int i = 1; i < m; ++i) {
        for(int j = 1; j < n; ++j) {
            pre_sum[i][j] = pre_sum[i][j-1] + pre_sum[i-1][j] - pre_sum[i-1][j-1] + matrix[i][j];
        }
    }

    // Debug output
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            cout << pre_sum[i][j] << ", ";
        }
        cout << endl;
    }
}

int sumRegion(int row1, int col1, int row2, int col2) {
    if (row1 == 0 && col1 == 0) return pre_sum[row2][col2];
    else if (row1 == 0) return pre_sum[row2][col2] - pre_sum[row2][col1-1];
    else if (col1 == 0) return pre_sum[row2][col2] - pre_sum[row1-1][col2];

    return pre_sum[row2][col2] - pre_sum[row1-1][col2] - pre_sum[row2][col1-1] + pre_sum[row1-1][col1-1];
}

}; Here, pre_sum is an independent vector<vector> that is part of the NumMatrix object. It is initialized in the constructor and then filled with the prefix sums. This way, pre_sum is completely separate from the input matrix and can be modified independently.

Why a Regular Member Variable is Preferred Independence: pre_sum should be an internal data structure that stores the prefix sums independently of the input matrix. Flexibility: Using a regular member variable allows you to reinitialize or modify pre_sum as needed, whereas a reference must always refer to the same object it was initialized with. Encapsulation: It helps in encapsulating the logic and data within the NumMatrix class, which is a good practice in object-oriented programming. Summary In your case, pre_sum needs to be an independent data structure that the NumMatrix class manages internally. Using a regular member variable for pre_sum achieves this, while using a reference would incorrectly tie pre_sum to the input matrix, limiting its functionality and independence.

Full text and comments »

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