I believe that I am not the only one who uses CF blog as a resource for learning things of CP and keeps track of good tutorials by marking those blogs as a favourite.

The problem I face is, each time I go to the list of my favourite blogs, it shows the title and a big part of the content of each blog. Since there are many blogs on my favourite list, it's hard to find the one I am looking for. Of course, I can search for words on the web page using CTRL+F, but I think it would be more convenient to have a list that contains only titles of my favourite blogs, like the Recent actions panels we have on the right.

If you think that's unnecessary, please suggest an alternative way to solve the issue. Thanks.

I have a 2D grid containing $$$n$$$ rows and $$$m$$$ columns. I can swap any two rows or any two columns any number of times (possibly zero). By swapping some rows or columns I can get different permutations of this grid. Lets's call permutations that can be achieved this way valid permutations. You can see that there are $$$n!m!$$$ valid permutations.

We know that each permutation can be represented as a product of $$$1$$$ or more disjoint cycles. For each integer $$$k$$$ in the range $$$[1, nm]$$$, I want to calculate the number of valid permutations that have exactly $$$k$$$ cycles. The bruteforce approach is iterating over all $$$n!m!$$$ possible permutations of the grid and counting cycles in each of them, which is a very slow solution and takes $$$O(n!m!nm)$$$ time. I want to find a more efficient solution (maybe dynamic programming or some combinatorial formula).

Constraints on $$$n$$$ and $$$m$$$ are not fixed. How to calculate this in a more efficient way?

Given a string $$$S$$$ , I want to find the number of different substrings of each length in the range $$$[1,|S|]$$$.

I can do it using LCP array which can be constructed using the Suffix Array of the given string. But I am trying to perform this task using Suffix Automaton.

Is it possible to do this using Suffix Automaton? If yes, then how?

I want to count the number of non-negative solutions of the equation: ax + by = c.

I know the naive approach where I can iterate over all non-negative y such that c - by is non-negative and count if c - by is divisible by a. Before starting iteration, I can check if c is a multiple of the greatest common divisor of a and b. If not, then I can simply return zero. But this will cost huge runtime for large values of a, b and c.

What is the most efficient solution for this?

I am trying to solve problem J of this gym contest.

In short, I am given non-negative integers n, m, a and k. I have to find such integers p and q that satisfies:
p > 0
q >  - 1
k + pa = n + qm

I wrote the third equation in this way:
pa + ( - q)m = n - k

Then using extended Euclidean algorithm I found such integers x and y that,
xa + ym = g, where g = GCD(a, m)

Multiplying (n - k) / g on both side we get:
[x(n - k) / g]a + [y(n - k) / g]m = n - k

Finally, I get p = x(n - k) / g and q =  - y(n - k) / g

The problem is, my implementation finds such x and y that resulting p and q violates the constraints p > 0 and q >  - 1.

For example, if n = 3, m = 5, a = 2 and k = 2, using extended GCD I am getting:
x =  - 2, y = 1 and then p = x(n - k) / g =  - 2, q =  - y(n - k) / g =  - 1.

But I need to find x = 3, y =  - 1 so that I can get p = x(n - k) / g = 3, q =  - y(n - k) / g = 1.

Here is my implementation of extended Euclidean algorithm:

int gcdExt(int a,int b,int &x,int &y)
{
    if (a==0){
        x=0,y=1;
        return b;
    }
    int p,q;
    int r=gcdExt(b%a,a,p,q);
    x=q-(b/a)*p,y=p;
    return r;
}

How can I change this function to find coefficients x and y that give such p and q that satisfies given constraints?

I was studying about matrix exponentiation here and it requires a prerequisite which says that I need to know how to find the nth power of a square matrix of dimension d in O((d^3)log(n)).

But I couldn't find any well-explained article on this topic. Can anyone please provide me with some links to blogs/articles that explain this technique?

Suppose, I have N distinct integers. I have to make M non-empty sets using these integers. An integer may not present in any of the sets and an integer can present in only one of the M sets. I have to print all possible ways to make M sets using these N integers.

For example, if I have N = 3 integers which are 1, 2 and 3, then there are 6 possible ways to make M = 2 sets:

1. {1} {2}

2. {1} {3}

3. {2} {3}

4. {1,2} {3}

5. {1,3} {2}

6. {1} {2,3}

How can I find out the number of ways to make M sets using N distinct integers according to the rule given above? What is the most efficient way to print all the possible ways?

I tried to solve this problem using dynamic programming, but I am having trouble to define DP states.

Recently I was trying to solve the problem Sum of MSLCM from ACM ICPC Live Archive.

After a little analysis, I found out that the answer is S — 1, where S is the sum of all X such that,

X = A * (int)(N / A) for all A in the range [1, N].

int ans=0
for(int a=1;a<=n;a++){
    ans+=a*(int)(n/a);
}

But my solution won't pass the time limit if I iterate over the range [1, N] as N can be as large as 20000000.

I couldn't find another solution even after several hours of thinking and decided to search for the solution on the internet. While searching for the solution I found the following code.

#include <bits/stdc++.h>
using namespace std;
#define long long long int
int main()
{
    ios_base::sync_with_stdio(false);
    long n;
    while(cin>> n && n){
        long ans=0,a=1;
        while(a<=n){
            long x=n/a;
            long y=n/x;
            ans+=x*(((a+y)*(y-a+1))/2);
            a=++y;
        }
        ans--;
        cout<< ans <<endl;
    }
    return 0;
}

This solution passed the time limit for the given input range and got accepted.

But I still couldn't understand the formula used in this code. The only optimization I see here is that it doesn't iterate over all the numbers in the range [1, N]. But how does that work?

I want a mathematical explanation of this solution.

I usually find the number of digit in the binary representation of an integer in the following way:

int digit = 1 + (int)log2(n);

I used to think that this way is absolutely correct as I never found any error. But today I got WA in problem number B (Codeforces Round 456) due to finding the number of digits in this way and I understood that this way isn't 100% correct. An integer n = 288230376151711743 was given in the case in which I got WA verdict.

While testing the error, I printed the 2 base log of 288230376151711743 using the log2() function of C++ and it printed 58. According to that 2^58 should be equal to 288230376151711743, but it isn't. 2^58 is equal to 288230376151711744.

So I guess, the value of log2(288230376151711743) is 57.99999999... or something like that which is very close to 58 and due to precision issues log2() function returns 58 in this case.

To avoid such errors I changed the way of finding the number of digits in binary in the following way:

int digit = 1 + (int)log2(n);
long long int x=(long long int)pow(2,d-1);
if(x>n) d--;

After changing my code in this way I got AC verdict, but I am still not sure about the accuracy of my way.

I want to know how much accurate is this way of finding the number of digits. If it is still not accurate, kindly suggest some other ways of finding the number of digits in the binary form of an integer which are accurate and efficient enough.

Somwtimes we use different user deffined data structures in C/C++. For example,

struct data1{
    string name;
    int id;
    double marks;
}

We can also use operator overloading and user defined functions in structers.

struct data2{
    string name;
    int id;
    double marks;
    
    bool operator < (const data &a) const{
        return id<a.id;
    }

    void addMarks(double x)
    {
        marks+=x;
    }
}

Using operator overloading or user defined functions makes the use of these structures easy.

Now my question is, when I declare an array or vector of a structure, will it allocate more memory if the structure contains some user defined functions in it?

For example, if I declare two vectors of the structures declared above ( data1 and data2 ) like given below, will they allocate same amount of memory?

vector <data1> v1(1000);
vector <data2> v2(1000);

Is the amount of memory allocated increases if the structures contains some functions in it?

I want to test a C++ program using a large input file which is in txt or other format and size of the file is almost 13 mb.

I tried the custom test option of Codeforces but it won't take files larger than 256 kb.

I just want to know that is there any online tool/compiler where I can run my C++ program with my large input file and get the execution time and memory used by the program?