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 >= 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://codeforces.net/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://codeforces.net/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

I worked on 8 and n. You can make all numbers (except 1 2 8 and n) 1 using i and n. By 6 operations at most by using 8 and n, you can turn n into 1, and 3 operations are needed to turn 8 into 1 by using 2 and 8. So n-4+9 operations would take it to solve

I'm not sure that this will pass systests, but I did something like for all values i from ceil(sqrt(n)) to n choose indices i, n, so they are now 1. Then choose indices n, ceil(sqrt(n)) two times, so n is now also 1. So, we reduced the problem to the same but ceil(sqrt(n)) instead of n, now repeat the process until all except 2 are ones.

mark 5 visits as 2 4 16 256 65536 n assuming n>65536. you can see that leaving this 5 pointers you need n-5 operations. and you can convert them to 2 1 1 1 1 in 10 operations thus total n+5 operations.

I did the following, for all numbers in the range 3 to n — 1 that are not powers of 16, perform the operation $$$(i, i + 1)$$$.

If there are $$$k$$$ powers of 16 less than $$$n$$$, this will take $$$n - 3 - k$$$, where $$$k \leq 4$$$ (as $$$2 \times 10^{5} \lt 16^5$$$ = $$$2^{20}$$$). Now, consider the sequence $$$16^1, 16^2, \ldots, 16^k, n$$$, we divide each term by the previous one, now each of these numbers are at max $$$16$$$ and we have used $$$(n - 3 - k) + k$$$ = $$$n - 3$$$ operations and have 8 operations left.

We have a $$$2$$$ (at $$$i = 2$$$), $$$k + 1$$$ numbers which are at max $$$16$$$ and the rest are $$$1$$$.

Now lets divide $$$k$$$ of these $$$k + 1$$$ numbers by the first $$$16$$$, making them all $$$1$$$. Now we have used $$$n - 3 + 4$$$ = $$$n + 1$$$ operations, and have $$$n - 2$$$ $$$1s$$$, one $$$2$$$ and one $$$16$$$, we can now use the remaining $$$4$$$ operations to divide $$$16$$$ by $$$2$$$ four times and get the required sequence.

Keep 1 and 2 as it is. Now let's convert all but Nth, 1st, and 2nd element to 1, by dividing by Nth element.
That's N — 3 moves, with 8 moves remaining. Notice that 2 * 10^5 cannot be reduced to 1 with 8 divisions by the second element.
Observation: Any number can be made 1 by 2 divisions using ceil(square-root). Lets keep 1st, 2nd, p1, p2, and N elements and make everything else 1, where p2 = ceil(sqrt(N)) and p1 = ceil(sqrt(p2)).
That's N — 5 moves. N can be made 1 with 2 divisions by p2, and p2 to 1 by 2 divisions of p1.
Now the total moves = N — 5 + 4 = N — 1.
Note that p1 is atmost sqrt(sqrt(200000)) = 22.
22 can be made 1 by 5 division of 2.
Total moves = N — 1 + 4 = N + 4

One of the approaches is the following: let $$$dp[i][j]$$$ be true if we can place first $$$i$$$ sections so that the $$$i$$$-th of them is on height exactly $$$j$$$, and false otherwise. The number of states in it is too much, so we need to improve something.

It can be proven that for every $$$i$$$, the values of $$$j$$$ such that $$$dp[i][j]$$$ is true form a consecutive segment (possibly empty, then there is no answer). So we can get rid of the second state and rewrite the solution as $$$dp[i]$$$ — the segment of values of $$$j$$$ such that the original $$$dp[i][j]$$$ is true.

It's just a sketch of the solution, we will provide a more thorough explanation in the editorial.

No one can do anything about that . Stop searching solution on youtube or ignore if it's published on web during the contest .

Each substring of $$$s$$$ having length $$$k$$$ forbids us to use its inverse as the answer (so, it forbids at most one string from being the answer to the problem). When $$$k = 20$$$, there are $$$2^{20}$$$ different strings that we may try as the answer, and that's why it always exists.

It looks like he tried to ruin the contest but he was only able to solve problem A lmao. But still, hope he got banned, I guess it's possible for hosts to search the same code and find this guy.

It is constructed in the following way: we have a binary number $$$111\dots11$$$ (exactly $$$200$$$ ones in this test, but there are other tests with different length of this number). The string $$$s$$$ starts with it. Then, we decrease this number by $$$1$$$ and append it to the right of $$$s$$$, then decrease again by $$$1$$$ and append again, and so on, until the length of $$$s$$$ becomes $$$10^6$$$.

hey, I tried this but either the approach doesn't work or my code has a bug: 102619406

edit: whoops i'm an idiot/it's too early in the morning... I was doing everything in reverse order

I did it that way and got accepted :)

Yes, I did that too. Our solution will take just n+3 moves. (Maximum).

Square root method should pass worst case is you get $$$[65537,257,17,5,3,2]$$$ or $$$[200000,448,22,5,3,2]$$$. Let $$$|S|$$$ = no of elements in this sequence.

no of operations = $$$n - 1- |S| + 2 * (|S| -1) = n + |S| -3$$$

mark 5 visits as 2 4 16 256 65536 n assuming n>65536. you can see that leaving this 5 pointers you need n-5 operations. and you can convert them to 2 1 1 1 1 in 10 operations thus total n+5 operations.

Yes, I have done that: https://github.com/actium/cf/blob/master/1400/60/1469d.cpp

The input should contain exactly one ( and one )

You don't need to look at the whole string of length k, just the last 20 should be enough.

Read question properly. (**There is exactly one opening bracket and exactly one closing bracket**)

Lol I did that too

I did that, will take a maximum of n+3 moves.

me too could not solve because of it

its painful, i saw after contest

The test case you included is not incorrect. The incorrect test case occurs at test case 11, or n=13. After the first 9 steps, the array has become all 1's except [1,2,3,13] at indices 1,2,3,13. After step 10, the array is [1,2,3,5]. After step 11, the array is [1,2,1,5]. After step 12, the array is [1,2,1,3]. We still need 2 more steps to get the desired array, yet your response only has room for 1 more step.

One of our solutions to this problem is greedy: replace the first several "?" characters with "(", until we have enough opening brackets, replace all remaining "?" with ")", and check that the resulting sequence is an RBS. It should work if there are more than one opening/closing brackets.