Yashraj1402's blog

By Yashraj1402, history, 9 months ago, In English

I have a doubt about the implementation of the Rabin-Karp Algorithm given on CP Algorithms.com

Problem: Given two strings — a pattern s  and a text t, determine if the pattern appears in the text and if it does, enumerate all its occurrences in O(|s| + |t|) time.

Solution:

vector<int> rabin_karp(string const& s, string const& t) {
    const int p = 31; 
    const int m = 1e9 + 9;
    int S = s.size(), T = t.size();

    vector<long long> p_pow(max(S, T)); 
    p_pow[0] = 1; 
    for (int i = 1; i < (int)p_pow.size(); i++) 
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(T + 1, 0); 
    for (int i = 0; i < T; i++)
        h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m; 
    long long h_s = 0; 
    for (int i = 0; i < S; i++) 
        h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m; 

    vector<int> occurences;
    for (int i = 0; i + S - 1 < T; i++) { 
        long long cur_h = (h[i+S] + m - h[i]) % m; 
        if (cur_h == h_s * p_pow[i] % m)
            occurences.push_back(i);
    }
    return occurences;
}

In the last comparison:

if (cur_h == h_s * p_pow[i] % m)
            occurences.push_back(i);

Why do we need to multiply h_s by p_pow[i], shouldn't it be just if(cur_h == h_s)

Please help.

Full text and comments »

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

By Yashraj1402, history, 16 months ago, In English

Problem Link

Why can't I flip all the 1's in the string, that way number of '01' substrings == number of '10' substrings == 0 ?

Full text and comments »

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

By Yashraj1402, history, 21 month(s) ago, In English

What rating problems should I practice to be able to solve Div2 C problem.

I have followed a pattern for practicing problems. When I started I used to practice 800 rating problems, then when I was able to solve A problem in 2-3 Div2 contests, I moved on to solve 1000-1100 rating problems and when I was able to solve B problem in 2-3 Div2 contests I moved on 1200-1300 rating problems.

But, I have noticed that most of Div2 C problems are of 1600-1700 rating (I may be wrong). So, should I start solving 1600-1700 rating problems? Also, will jumping from 1300 to 1700 be actually beneficial for me?

Info which might give you insights to my level

Highest rating: 1201

Current rating: 1159

Number of 1200-1300 problems solve: 70(1200), 15(1300)

Full text and comments »

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

By Yashraj1402, history, 3 years ago, In English

Problem Link

My Approach:

Only make the first element of vector A less than vector B. So if B[0] < A[0], iterate over A and find the first element smaller than B[0] by this we will also know the number of swaps required to change the first element of A. Then iterate over B and find the first element greater than A[0] by this we will know the number of swaps required to change the first element of B. Print the minimum number of swaps.

solution Link ,546th test case fails.

Full text and comments »

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