It teaches how to understand someone else's codes,, which is very important part of learning CP.

And desirable to grow up

very true pfp XD

Hoping to become specialist...and very relatable pfp...

:sadge:

You have a nice rating graph, unlike me :P

what do you mean?

This comment didn't deserve downvotes. :(

It has been published here

Happy Birthday!!! Best of luck for today's contest.

Happy birthday! Good luck!

its a system used to prepare the problem set

I have practiced hard, definitely going to be green.

goodbye 2020 is still there friend

please change your profile picture first , why u put such profile pictures on a platform like codeforces it doesn't make sense at all , please change it!!

MikeMirzayanov can you please ban this guy? He has had this profile pic for months now.

does it even matters whatever profile picture it is unless it's NFSW, which this one is clearly not, Be a bit tolerant to other cultures and choices

First 4 problems look like not less 1700 of difficulty. Quite easy round

[rev 2] ok

This proves CP really makes u good at noticing patterns . lol

No

This is how I did it — First make all the numbers from 3 to n-1 (excluding 8) 1 by the operation "i n" (where 3 <= i <= n-1 and i not equal to 8). Now transform n to 1 by the operations "n 8". Finally make 3 "8 2" operations to transform the 8 to 1.

The first step would take n-4 operations. The second step would take at most 6 operations and the final one would take exactly 3 operations. (n-4) + 6 + 3 = n+5

To see that the second operation would take at most 6 operations, note that n is at most 2e5 < 2^18

If n<=32, divide every number from 3 to n-1 with n and then continuously divide n with 2 until it becomes 1.

if n>32, divide every number from 3 to n-1 except 32 with n and continuously divide n with 32 until it becomes 1 and then continuously divide 32 with 2 until it becomes 1.

When I said divide 'a' with 'b', I meant ceil(a/b).

how to understand c (english)?

like a chain fall down (QAQ

Keep maximum and minimum possible heights of sections, or rather the y-coordinates of their bottom. Let's call minimum coordinate d and maximum coordinate u. For section i it's possible to choose y-coordinate in segment [max(a[i], d-k+1); min(u+k-1, h[i]+k-1)] where h[i] is height of place for i-th section. Then d = max(a[i], d-k+1) and u = min(u+k-1, h[i]+k-1)

Don't forget that the last section must lay on land (coordinate y=a[n-1])

Something like that, create the low and high boundary and check for rules

   low[0] = high[0] = ground[0];

   bool good = true;

   for (ll i = 1; i < n; i++)
   {
       low[i] = max(low[i - 1] - k + 1, ground[i]);
       high[i] = min(high[i - 1] + k - 1, ground[i] + k - 1);

       if (high[i] < low[i]) {
           good = false;
           break;
       }
   }
   if (good) {
       if (ground[n-1] < low[n-1] or ground[n-1] > high[n-1]) {
           good = false;
       }
   }

Calculate the highest possible (fence $$$k - 1$$$ from ground or last fence) and lowest possible (fence on ground or $$$k - 1$$$ below last fence) height for the bottom of the fence at each position, using the highest and lowest possible height for the previous position. At each position we should have $$$h \gt = l$$$, and also in the last position we should have $$$l = H_n$$$.

After 1 day most of the time . But till then most of the solution would have been discussed here.

Suppose n=k=3 and s=111, you're saying the answer is mex({111}) = 000?

Edit: I missed "invert the input string"; should be mex({000}). Nice solution.

Another way:

Let m be the smallest integer such that 2^m > n+1-k (number of substrings). Consider last min(m, k) inverted bits of every substring; select smallest unused mask.

I solved E using string hashing.

Create an empty set "se" of data type <pair<long long, long long> >, and store the hashes of complements of all substrings of s of size k in se.

For each substring, one hash corresponding to modulo 10^9+7 and one corresponding to 10^9+9 are stored as pair elements. This can be done in O(n) if we keep using the hash of the complement of the previous substring while iterating from 1st to last substring of size k.

Now in set "se", we have the hash pairs which our result string t cannot take. These elements are at most n-k+1. So, if we start constructing t by iterating from 0 to n-k+2 in binary form, we will get the answer in at most n-k+2 operations. While iterating from 0 to n-k+2, the first binary string t whose hash pair does not match any pair element from the set is the answer.

Find the max prefix in array 1 and array 2 and just output its sum

Just try paring each prefix of R and each prefix of B (two for loops) and sum the prefixes up. Update the best solution as you do this.

Yes, there is a solution using dp.

The problem can be described as: Find the prefix that has the largest sum in an array that can be formed through two other.

Therefore, we can make a dp[i][j], with i the index of array r and j the index of array b.

In a dp state, we have two options:

1- add r[i] to the array and increment i. 2- add b[j] to the array and increment j.

if I have already pre-calculated dp[i][j] before, I can stop because the answer for the remaining suffix has already been calculated.

My code: https://mirror.codeforces.com/contest/1469/submission/102568792

You can solve B using a greedy algorithm, take the max prefix sum of blue and max prefix sum of red. You can be sure it will always work because you want to maximise sum of a prefix of list a. You also know that orders of b and r are fixed so taking the maximum prefix sum of those lists will always be optimal There also exist a (much slower) dp solution which I coded https://mirror.codeforces.com/contest/1469/submission/102569441

Line: l = max(a[i]+1-k-(k-1),0LL);

in your loop the minimum starting position depends on reachable minimum of last block, not a[i]+1-k (it may be not reachable)

Well, you can solve B with dp, and one of the approaches to C is to consider dp solution and get rid of the second state