Brother, the person who cheated has posted an apology. I just thought you should know.

dp[i][j] = dp[i - 1][j - 1] + s1[i];

This is the part which is causing TLE in tour code. Since N can be upto 3000 and you are running 2 for loops so it becomes 9 * 10^6 = 10^7 (approx). Till here it is fine but you are also copying string of previous dp state in current state which is taking extra O(string length) time inside your loops. For dp[i][j] = dp[i-1][j-1] + s1[i] first your code copies the string in dp[i-1][j-1] in dp[i][j] then it adds an extra character to it and copying and pasting a string takes O(n) times.

Ok so assume you have 2 arrays [1, 2, 3, 4] and [0, 1, 2, 3] what do you think which one of them will have max value of mex1

Array 1 will have mex = 0 and array 2 will have mex = 4.

Intuition :- It is best for us to make array elements as low as possible till zero and all the elements must be unique. This will ensure all the small elements are present in the array so the mex can be as large as possible.

Now combining all info above.

Let's assume you have an array [6, 2, 6, 4, 18]

For this to calculate the optimal array we need to calculate their gcd which is 2.

So optimal array looks like [0, 2, 4, 6, 8] if I tell you to find it's mex5 so the answer is 9

But we can also form our final array somewhat differently like [0, 4, 6, 8, 10] or [2, 4, 6, 8, 10] and mex5 in both the cases will be 7.

Why :- Because we ignored to form 1 more possible small number which minimized our mex value.

I hope you can understand this. If this is not clear now also then you can again message me I will try to help as much as I can.

Actually there is a concept named Linear Diophantine Equation similar to this. You can look it up on Cp algorithms. Hope it helps.

Dominator orz, please calm down, I can't see my idol frustrated.

So there is a basic concept. If I give you 2 numbers like 2 and 3 and say you that you can use 2 and 3 any number of times and you can either add them or subtract them then what are the possible numbers you can generate.

Answer :- You can generate any integer from 2 and 3.

Reason :- GCD of 2 and 3 is 1 therefore you can use 2 and 3 to create 1 (3 — 2)

Now for any integer x you can generate it by using (3 — 2) x times.

Now take 2 and 4 for example. Their gcd is 2 so you can generate 2 from them (4 — 2). Now you can generate any even number from its gcd by repeating (4 — 2) any number of times but you cannot make any odd number using it.

Go in G after taking gcd of all, suppose gcd is x therefore optimal array to form will be [x, 2x, 3x, ... ]

Sorry if I made you more confused by my explanation but if your doubt is not cleared I will try to explain with a different approach.

Decoded message for the binary pattern at the end.

I wish you all good luck for div 4.

The constraints on n is 1 <= n <= 10^18 so in loop you had to use i < 64 but you used i < 32 bits which resulted in wa

For people why LCS is not working for problem b actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
}
for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);

Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
}
for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);

Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
}
for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);

Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
}
for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);

Thanks everyone for clearing my doubt.

Can anyone explain me how penalty works in Div 3. "Note that the penalty for the wrong submission in this round is 10 minutes.", I am confused what this 10 minutes means.

Cauchico orz

Did anybody say one piece :)