I have seen many people saying that "They love to do competitive programming" but I would like to go a bit deeper in this thought. I want to know "What do you like when you say I love competitive coding?". Is it the process that "you try to do some problem, you think about some approach, it turns out to be wrong, then you try different approach, not within bounds, thinking for some other approach" or something else?

I am asking this question because personally, I have found that I would like to do some work as long as the response is positive. In competitive coding, if I am able to solve questions I would want to try more and more but as soon as I encounter some problem for which I am not able to think any approach, suddenly my mind shifts to do some other thing. It also happens in other places also, like when I am playing CSGO I would like it till the point I am winning.

I know that in order to learn you have to go out of your comfort zone, but when 4-5 problems come in which I was not able to come up with any solution and after seeing editorial it becomes obvious, then I begin to doubt my practice and this question starts coming in my mind. If anyone would like to provide some suggestions in this, then it would be very helpful for me in lot of things.

Thanks

Hello everyone, I am trying to solve Required Substring problem from CSES.

I thought about a combinatorial solution for the problem. My idea was that for every $$$i < n$$$

• if $$$i$$$ does not divide $$$n$$$, then there would be total $$$n$$$ arrangements which would be similar, so we would have to count $$$ways = \frac{\text{# of arrangements}}{n}$$$ in it, for ex, in sample test case, $$$n=4, m=3$$$, arrangement, {$$$1,1,1,2$$$}, {$$$1,1,2,1$$$}, {$$$1,2,1,1$$$}, {$$$2,1,1,1$$$} would be considered similar
• if $$$i$$$ divides $$$n$$$, then there would be total $$$i$$$ arrangements which would be similar, so we would have to count $$$ways = \frac{\text{# of arrangements}}{i}$$$ in it, for ex, in sample test case, $$$n=4, m=3$$$, arrangement, {$$$1,2,1,2$$$}, {$$$2,1,2,1$$$} would be considered similar

So, I am iterating from $$$0$$$ to $$$n-1$$$, and if current period is prime and it divides total number of pearls $$$n$$$, then we can subtract the number of arrangements which it can form, from total number of arrangements and add the number of ways to the answer. We should also check whether, current period is prime because the period for $$$4$$$ would be same as $$$2$$$

int allWays = pwr(m, n);
int ans = 0;
for(int i=1;i<n;i++) {
    if(isPrime[i] && n % i == 0 && i <= m) {
        int iLengthPeriod = nPr(factorialArray, m, i);
        allWays = (1ll * allWays - iLengthPeriod + mod) % mod;
        ans = (1ll * ans + (1ll * iLengthPeriod * inverse(i)) % mod) % mod;
    }
}

ans = (1ll * ans + (1ll * allWays * inv(n)) % mod) % mod;
cout << ans << "\n";

Surprisingly, my code worked for smaller test cases, but it is giving wrong answer for large test cases. I checked the modular operations also and the factorial and prime conditions, but cannot figure out the issue. If anyone can help me out in this, I would highly appreciate it.

Thanks

Hello everyone, I am trying to solve Required Substring problem from CSES.

First of all, I tried to solve it using combinatorics. My idea was that consider $$$n=6$$$ and string $$$s=$$$ABCDB with 5 characters, then the number of ways we can make $$$n$$$ character string with string $$$s$$$ in it, would be to fix string $$$s$$$ at first position in $$$n$$$ characters and fill rest positions with $$$26$$$ characters, giving $$$numberOfWays = 26$$$. Then, we can shift the substring for $$$(n - m)$$$, i.e, $$$6 - 5 = 1$$$ times to right, and we would get $$$numberOfWays = (n - m + 1) * 26^{(n - m)}$$$, which would, for sample test case, result in $$$numberOfWays = (6 - 5 + 1) * 26^{(6 - 5)} = 52$$$

But, it failed for this test case $$$n=6$$$ and $$$s=$$$ AA. And, I am not able to figure it out, why this is not working because of the large output.

Then, I peeked the solution here, and tried it to code myself, but in the end it is not working. My idea was same as the solution, that is, to build string character by character, and we track progress of building required string as our substring.

int recurse(int in, int maximumMatchingPrefixLength, int n, int m, int numberOfRequiredSubString) {
    if(in == n) {
        return numberOfRequiredSubString > 0;
    }

    int ans = 0;

    // matching case
    if(maximumMatchingPrefixLength+1 >= m) {
        // insert the last character, and now maximum matching prefix would become 0
        // and number of required substring would increase by 1
        ans += recurse(in+1, 0, n, m, numberOfRequiredSubString+1);
    }
    else {
        // insert that character, which is matching to next character after maximum matching prefix
        // for ex, required substring = ABC
        // and current string is XGAB
        // then, we are inserting C here
        ans += recurse(in+1, maximumMatchingPrefixLength+1, n, m, numberOfRequiredSubString);
    }

    // non matching case
    // insert all those characters, which are coming after any prefix length of Required string
    // and recurse for next position, with that prefix length
    set<char> uc;
    uc.insert(s[maximumMatchingPrefixLength]);
    maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength - 1];
    while(maximumMatchingPrefixLength > 0) {
        uc.insert(s[maximumMatchingPrefixLength]);
        ans += recurse(in+1, lps[maximumMatchingPrefixLength-1], n, m, numberOfRequiredSubString);
        maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength-1];
    }    
    
    // insert other characters, which did not come till now
    ans += (26 - uc.size()) * recurse(in+1, 0, n, m, numberOfRequiredSubString);

    return ans;

}

And, the Solution is following slightly different approach.

ll solve(int i, int n, int j, string &s)
{
    if(done[i][j]) return dp[i][j];
    done[i][j] = true;
    if(i == n) return dp[i][j] = (j==(int)s.size()?1:0);
    if(j == (int)s.size())
    {
        return dp[i][j] = (mxK*solve(i+1,n,j,s))%mod;
    }
    ll ans = 0;
    int t;
    for(int k = 0; k < mxK; k++)
    {
        t = j;
        while(true)
        {
            if(k == s[t]-'A')
            {
                t++;
                break;
            }
            else if(t)
            {
                t = kmp[t-1];
            }
            else break;
        }
        ans += solve(i+1,n,t,s);
        ans %= mod;
    }
    return dp[i][j] = ans;
}

I think my code is faulty at many places but if someone can tell what mistakes my code is doing, or even the main problem of my code, then it would be really helpful for me.

Thanks

Hello everyone, I am trying to do Sliding Window Median problem from CSES. I have thought of multiset approach which is pretty close to one of its solutions and wrote this peice of code.

int l=0, r;
for(r=0;r<n;r++) {

    if(!up.empty() && *up.begin() <= a[r]) {
        up.insert(a[r]);
    }
    else {
        low.insert(a[r]);
    }
    
    if(up.size() > low.size()) {
        low.insert(*up.begin());
        up.erase(up.begin());
    }

    if(up.size()+1 < low.size()) {
        up.insert(*low.rbegin());
        multiset<int>::iterator itr = low.end();
        itr--;
        low.erase(itr);
    }
    
    if(r >= k-1) {
        
        cout << *low.rbegin() << " ";
        if(!low.empty() && low.count(a[l])) {
            low.erase(low.find(a[l]));
        }
        else if(!up.empty() && up.count(a[l])) {
            up.erase(up.find(a[l]));
        }
        l++;
    }
}
cout << "\n";

When I ran it on larger test case, it is taking this much time.

real    0m50.343s
user    0m50.003s
sys     0m0.195s

And, on the running the USACO solution, following same approach.

void ins(long val) {         // insert val into sets
    long a = *low.rbegin();  // current median
    if (a < val) {
        up.insert(val);
        if (up.size() > M / 2) {
            low.insert(*up.begin());
            up.erase(up.find(*up.begin()));
        }
    } else {
        low.insert(val);
        if (low.size() > (M + 1) / 2) {
            up.insert(*low.rbegin());
            low.erase(low.find(*low.rbegin()));
        }
    }
}

void er(long val) {  // erase from sets
    if (up.find(val) != up.end()) up.erase(up.find(val));
    else low.erase(low.find(val));
    if (low.empty()) {
        low.insert(*up.begin());
        up.erase(up.find(*up.begin()));
    }
}
low.insert(arr[0]);
for (int i = 1; i < M; i++) ins(arr[i]);
cout << *low.rbegin() << " ";
for (long i = M; i < N; i++) {
    if (M == 1) {
        ins(arr[i]);
        er(arr[i - M]);
    } else {
        er(arr[i - M]);
        ins(arr[i]);
    }
    cout << *low.rbegin() << " ";
}

It is taking this much time.

real    0m1.396s
user    0m1.178s
sys     0m0.214s

Now, I am not able to understand that why the time taken is increasing so drastically, even though the complexities are same. I can share the complete code also if it would help. Thanks