Hello Codeforces!

On Dec/28/2020 17:35 (Moscow time) Educational Codeforces Round 101 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | jiangly | 6 | 121 |

2 | Geothermal | 6 | 138 |

3 | neal | 6 | 138 |

4 | kotatsugame | 6 | 165 |

5 | tute7627 | 6 | 177 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | dorijanlendvaj | 72:-13 |

2 | star_xingchen_c | 56:-1 |

3 | johnwick2b67 | 26:-5 |

4 | yash_daga | 21 |

5 | lsantire | 20:-2 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | Mprimus | 0:01 |

B | Geothermal | 0:02 |

C | I_love_Tanya_Romanova | 0:08 |

D | abc864197532 | 0:12 |

E | Kerim.K | 0:18 |

F | jiangly | 0:42 |

**UPD:** Editorial is out

What the meaning of Educational rounds? I think that the meaning is hacking education, this contests teach to hack

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

Why it's important? I did hacking in Educational 1-2 times

I think that one of most important — write code fast and without bugs

You can consider hacking as Debugging practice

Solving one more problem would always benefit more lol

It varies from time to time. Sometimes a few minutes before the contest end, even high rated coder try to hack instead of solving one more problem. Because they guess it's not enough time to solve the last harder problem. So, they try to increase some points. And, the educational hacking phrases can be practice for the fruitful use of those few minutes.

Yeah I mean he/she is just being salty, not thinking of improving but just complaining

one of the things that improves your debugging skill is the debugging of other people's code.

Pupil comments something: 8 downvotes (as of posting this comment)

Red comments the same thing: 49 upvotes (as of posting this comment)

LOL

People want to know who writes things rather than what has written.

Exactly!

Our time will also come, if we keep doing practice.

Discrimination by rating

Stop ratism... #PLM(Pupil Lives Matter)

LMAO

I hope it is easy enough to change the rank:):)

And desirable to grow up

Hoping to become pupil again

very true pfp XD

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

2 points to master. I expect to become orange to New year

:sadge:

You have a nice rating graph, unlike me :P

Educational Codeforces Round 5

what do you mean?

Binary Representation of 5 is 101

This comment didn't deserve downvotes. :(

Hoping to have a wonderful round and becoming a specialist again

When the editorial will be published? Amazing round!

It has been published here

It seems like it was taken down and replaced with a youtube video called "Rickrolld". Can you please re-post it? I really want to see the editorial!\s

Me too. So that to pry the answers and then solve all problems fast

r/whoosh

r/wooosh

https://en.wikipedia.org/wiki/Rickrolling

Today is my birthday. I hope to reach specialist. Wish me guys!! And I wish all the best for all those giving this contest!!

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

Happy birthday! Good luck!

is Polygon is a different site like codeforces?? i dunno about that

its a system used to prepare the problem set

.

I have practiced hard, definitely going to be green.

it is a palindrome round 101

i hope it be easy :D

last round of this decade...want to give our best...

goodbye 2020 is still there friend

Excited for the round. Aiming for green. Hope it will be really "educational"

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.

MikeMirzayanov

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

It looks pretty NSFW, especially the smaller version...

Yet another div 1 round in disguise

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

Could you please explain how to solve problem C (without dp transition)? It took me more than an hour just to even understand the theoretically implausible picture of the problem.

Keep minimum and maximum y-coordinates of the bottom of next section, based on current altitude and previous minimum and maximum values

You store maximum and minimum height for a segment to be added to the prefix.

Questions of this round to me:[rev 2] ok

you did not solve it i was asking him for the rev 1 not the 2 :)

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

does the hack make u increase in ur points in the edu rounds

No

(After contest) How do you solve D?

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`

Brilliant, thanks for it!

really nice solution, i was trying using sqrt($$$n$$$) instead of 8 and the operations were exceeding $$$n$$$ + 5.

sqrt(n) works too

codeyeah, it's working because of ceil which i figured out later, floor won't work or maybe i made a mistake while calculating operations.

How did u decide on 8? I was thinking of 64 and 128 but the operations were exceeding n+5

Well, I sequentially tried 2, 4 and then 8 and then 8 worked for me so I stopped there.

I thought of this, but I did not have time to implement it and it seemed a bit hacky :(

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 solve c ??

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

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$$$.

what if the Hn is higher tan r[n-1]+k-1 ?

Then it's impossible. I set $$$h = min(H[i] + k - 1, h + k - 1)$$$ and $$$l = max(H[i], l - k + 1)$$$. In that, case $$$h < l$$$ so we output NO.

When the editorial will be published? Amazing round!

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

I didn't manage to code it, but I know how to solve E with Suffix Array. You start by inverting the input string. What you want is the mex of all substrings of size k. After sorting the suffixes, there is a lemma that says that on average, adding one to a binary string does 2 operations. By using these, you can solve the problem

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.

No. I said I am starting by inverting the string.

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.Well yes, but I think you still have to check that all prefixes of the substrings of length k are equal to 0 up to the value of that unused mask.

Yes, I forgot to mention that a substring can be skipped if the first

`k-min(m, k)`

bits aren't all 0 (after inversion).Code: 102623431

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.

I haven't understood the last part (i.e. how to find t from the set se), can you explain it in a detail?

Anyone know what test 83 of E is?

Edit: Got it, suppose $$$n = 10^6$$$, then our check length for the mask will be 20 bits. While we may think of checking all subarrays [x — 19, x] for $$$x \geq 20$$$ is the logical one to find all subarray end masks, the mask generated by any subarray checked before $$$[k - 19, k]$$$ where $$$(k \gt 20)$$$ will never actually be at the end of any subarray and shouldn't be counted as a mask that need be satisfied for bit similarity.

How to solve B ?Is there a dp solution for it?

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

I tried to solve C by creating minimum and maximum starting position for next section . Could some one help me where i am wrong . Submission

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)

Before that i have checked if a[i]>l .Now if a[i]>l then we can use that formula right ?

D was easier than C

you people can never make good problems how is this round educational? No DP/ graph till 4th. question. Please change the name of these rounds as Adhoc-edu rounds.

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

OH! really means you understand prefix sums as dp in B. may be C will be a good DP. but that will be a third world solution please come in reality man!

There is a DP solution for B https://mirror.codeforces.com/contest/1469/submission/102569441

For C I have a solution that I don't know how to prove. I am interested in how the official solution approaches it.

What is the intuition behind D? I thought of divide and conquer but couldn't think of a good solution.

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

Thanks, well explained! But I wonder why were you changing array elements(except p1&p2) in your solution which I guess was not required. Any reason? (Just curious)

I had used it to run verifier for first 10k [1 to 10000] and last 1000 [2*10^5-1000, 2*10^5] using asserts. You can refer to the commented code for the verification.

Was C a DP problem? It looked like it at first but none of the top solutions have used DP

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.

Bruh is the official solution to E hasing? I had suffix array but didn't manage to code :(

Hashing, Suffix ArrayQueue go brrr: code.

you genuinely know/searched for the ascii code of '0'. Nice

Lol I learned some cute tricks like that from reading tmw's code too often.

The official solution doesn't use any string algorithms.

The idea is the following: there is always an answer when $$$k \ge 20$$$ (each substring of length $$$k$$$ forbids at most one string from being the answer), so we are interested in at most $$$20$$$ last characters of the answer (all others can be zero). I check each substring of length $$$20$$$ and determine which combination of last characters it forbids from being the answer (be careful: there may be zeroes before these $$$20$$$ characters in $$$s$$$, and it may mean that this substring actually doesn't forbid anything since the prefix of the answer will contain $$$k - 20$$$ zeroes). I have marked some combinations of last characters as forbidden, so all that's left is to find the minimum unforbidden combination.

The implementation I provided is a bit different since I use something like $$$\lceil \log_2(n - k + 2) \rceil$$$ instead of $$$20$$$. It runs in something like $$$O(n \log n)$$$.

I understand. To check if the first n — k — 20 characters are '1' I am guessing that you are using hashes. Thank you!

No need for hashes, just precalculate the closest position of $$$0$$$ to the right/left of each index.

Making fun of less rated participants is not helpful.

I didn't make fun, it is the exact way I approached this problem when I first heard about it.

Plz explain dp solution also in detail in problem C editorial.

The solution for ques A was already uploaded on Youtube while the contest was going on. This is very unfair with those who seriously give the contests. It should be made unrated.

https://www.youtube.com/watch?v=iiCJIBGaqhk

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

Why there is always a soultion in $$$E$$$ for $$$k > 20$$$??? I have seen many solutions use this and couldn't understand why?

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.

Got it, thanks for the great problem.

this guy uploaded answer for question A while the round was still going on https://youtu.be/iiCJIBGaqhk

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.

What the fuck is the testcase #43 in E and how did it fucking kill my solution?

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$$$.

The fact that you are responding to so many comments is really helpful. Thank you!

Thanks a lot! Found a stupid bug in my code and I'm just dumbass

I tried to solve problem C by storing maximum height a block can go and minimum height which is required ,can someone tell me where I am wrong. these is my solution.**Please help me** I still can't get it.

Problem D: I see many different submission for D. Has anyone else also done by takingsquare rootrepetitively? I think it will pass, as repetitively square rooting should not take more than 5 rounds, not sure.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

I am trying to hack A , it shows this input is invalid how ?

1

(()?

The input should contain exactly one ( and one )

102622037 How to reduce memory here?

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

Problems such as this can occur. 100000000000000000001 was the substring but we saved 000000000001 's occurrence and this cant become answer when it would have

D is one of the most beautiful question I have seen so far.

Please someone explain question 1. If ((() give YES as the answer then how ??

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

If I would have got 10 more minutes,

D was crackedFor problem D, did anyone else take just the indices n and ceil(n^((sqrt(5)-1)/2))? It works but there are a few corner cases. Head bashing that I didn't get the direct square root solution.

Lol I did that too

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

Was it just me , who didn't see the "exactly one" part in problem A, for a very long time.

me too could not solve because of it

its painful, i saw after contest

Could anyone please explain why this code prints wrong output compared to my local execution environment? (Problem D)

http://mirror.codeforces.com/contest/1469/submission/102626247

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.

Thanks for the reply! Actually I misunderstood that 'Output' was an answer and 'Answer' was my output ;)

For problem A, what if there are at least one ( and at least one ) rather than "exactly"?

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.

Almost same problem with this — 1153C - Serval and Parenthesis Sequence

Almost same problem but with costs for replacing involved — D. Least Cost Bracket Sequence.

I basically copy pasted my solution for that with costs replaced by (0, 0). Problem is that I don't know how to read problem statements :(

you can still solve for given constraint using brute force .submission . I didn't read that "exactly" during the contest and thus solved for at least .

If you got WA on test 2 and have no clue why, there's a chance you might have missed the second condition (at least I did):

the only Educational thing I learnt from problem A was to read problem statement again and again.

Why are people with rating >=2100 in the official standings? I wanted to see how I'm standing against other Div. 2 coders but I can't find a way to do it.

After the hacking period is over , and the system testing is done , there will be a option in the standing page where you can choose div1 , div2 or both.

I'm getting Invaild input format while hacking a submission.

Is there any format which we have to follow..?

You have to follow the format and the bounds in the problem statement. You may have forgot to include the number of test cases in the input, or maybe one of the numbers is greater than or less than what the problem statement allows.

my input is in given range only..

i'm giving like this below example:

That's it.!

Do i have to provide expected output.?

You don't need to provide expected output, but I would recommend you to read the problem statement again. For example, in task A you might have missed that there must be exactly one '(' and exactly one ')' in each test case.

if you are hacking A problem then read the problem correctly string s have exaclty one '(' and one ')'

if you are giving testcase as

1 (((())

then its wrong

Thanks, man! I didn't realise this and was wasting my time trying to hack.

Actually I can't understand why this contest's called educational

It was written twice "**There is exactly one character ( and exactly one character )**" in front of my eyes.I can't believe that, still not noticed it carefully who else faced that...

Good contest, thanks to the organisers. Some tricky but interesting problems. I made a right mess of A! Disappointed not to get E due to TLE but I think I am one of many — I spotted the 'reduce K to 20' trick, but I think using pypy was my downfall, along with the (very) large limits — wasn't able to get my constant factor down enough for pypy. Also serves me right for not being good enough at C++ I guess :)

Edit: Wrong

Could you explain why? In my critical loop, I cannot see anything that evaluates 2^20 different options. I see O(N*20) for each test case, but we know that sum of N over all Q cases is capped to (about) 2^20, so if Q is large then it will not be doing anything like 2^20 calculations. I'm probably missing something — would be grateful if you could show me what that is.

I checked again and looks like I miscalculated the complexity of your code. My bad :(

My very first comment on CF pls don't downvote

okay, but what's the point of your comment ?? I asked a genuine doubt some other day and got downvoted.

Parade of Invalid input in A XD

we all misread A didint see two brackets acquired exactly once :(

they should have mentioned it in quotes. '(' and ')'

Here are some video solutions for all problems, with the added bonus of struggling with a writing tablet

In problem A on

test case: (((),

this guy's solution gives YES, whereas this guy's solution gives NO. And interestingly, both are ACCEPTED ..... Something FISHY! Don't KNOW!

Not a valid test case. The inputs must have exactly 1 '(' and exactly 1 ')'

Ooh the way the question is written is misleading then....

And why different solution for same test cases...

You can get different solutions for the same test case if the test case is invalid since one solution may not work for all inputs in general, but relies on an assumption that the restriction given guarantees.

Everyone who is trying to hack A's submissions, please note this ->

There is exactly one character ( and exactly one character )Honestly I don't get how everyone is missing this, it's written in bold in the statement twice

D easy solution (for given constraints): If n <= 8: Go bruteforce Return;

From 3 to n-1 divide all by n except 8. (We are left with 2, 8, n)(n-4 operations) Divide n by 8 till it becomes 1 (at most 6 operations) Divide 8 by 2 (3 operations) Done. Finally, n-4+6+3 = n+5

Thanks for the problem D!

With my group of high school students, we routinely discuss solutions after Codeforces contests. This time, the three solutions we had for D were attacking the problem from different angles: repeated square root, a few powers of two, and leaving only two non-unity elements. Loved it.

I honestly feel that was hardest problem in the round for me today! Took me like 30 mins to construct square root solution, but when I found that, was very beautiful. What are other approaches?

Also surprisingly F was the easiest among D, E, F :( Sad I had only 5 mins left when started it.

EDIT: Above comment shows the solution with 2, 8, n, which seems to be very nice and way simpler than mine.

In every solution, we can destroy (reduce to 1) every element except the last in one operation, dividing it by the next element, or by the last element.

The "few powers of two" solution is as follows:

Suppose we leave $$$2$$$, $$$2^2$$$, $$$2^4$$$, $$$2^8$$$, and $$$2^{16}$$$ undestroyed. Then each of them except $$$2$$$ can be destroyed by the previous one in two operations.

Now, take only those which are $$$\le n$$$, and substitute the last of them by $$$n$$$ itself. Then, $$$n$$$ can be destroyed in four operations, and all others still in two operations. Turns out it is enough.

The "two non-unity elements" solution is as follows:

Let us destroy all elements except $$$n$$$ and one other, $$$x$$$. The remaining problem is then to pick $$$x$$$ so that the pair $$$(x, n)$$$ can be reduced to $$$(1, 2)$$$ fast. The reduction is dividing the greater number by the lesser one until the pair becomes $$$(1, 2)$$$ or $$$(2, 1)$$$. For example, $$$(12, 5) \rightarrow (3, 5) \rightarrow (3, 2) \rightarrow (2, 2) \rightarrow (2, 1)$$$ takes four steps.

Some pairs are too slow: $$$(200\,000, 2)$$$ requires 18 steps.

Some pairs are plain bad: $$$(3, 9) \rightarrow (3, 3) \rightarrow (1, 3)$$$ never goes to $$$(1, 2)$$$.

But for the good pairs, just how fast it can be? Let us follow the division process backwards:

$$$(1, 2)$$$ can result from $$$(2, 2)$$$,

$$$(2, 2)$$$ can result from $$$(4, 2)$$$ (or from $$$(3, 2)$$$, but let us look at the greatest possible value for now),

$$$(2, 4)$$$ can result from $$$(8, 4)$$$,

$$$(4, 8)$$$ can result from $$$(32, 8)$$$,

$$$(8, 32)$$$ can result from $$$(256, 32)$$$,

$$$(32, 256)$$$ can result from $$$(8192, 256)$$$,

$$$(256, 8192)$$$ can result from $$$(2\,097\,152, 8192)$$$.

So, in seven steps we have, we can destroy up to $$$n = 2^{21}$$$. Side note: the quantities are of the form $$$2^{F_n}$$$, Fibonacci powers of two.

With some monotonicity and hopeful handwaving, every number less than $$$2^{21}$$$ is also covered. But by which $$$x$$$, exactly? As the $$$(3, 9)$$$ example above shows, we can't just pick any and hope for the best. Turns out we can find such $$$x$$$ by brute force: the number of steps for each $$$x$$$ to try to reduce $$$(x, n)$$$ to $$$(1, 2)$$$ is logarithmic at worst. So, the whole solution works in $$$O (n \log n)$$$.

The fact that the solution exists for every possible $$$n$$$ up to $$$2^{21}$$$ I did not rigorously prove, but checked after the contest, in $$$O (n \log n)$$$ also, by two pointers on $$$n$$$ and $$$x$$$ going down. As the "best" possible pairs $$$(x, n)$$$ look like $$$(2^{F_k}, 2^{F_{k+1}})$$$, a value $$$x$$$ near to $$$n^\varphi$$$ fits, where $$$\varphi = \frac{\sqrt{5} - 1}{2}$$$.

Nice explanation for the two non-unity elements solution. I found $$$x$$$ by guessing $$$x=\lceil{\sqrt{n}\rceil}$$$ but that took too many operations (200007 for $$$n=200000$$$) so I figured I wanted to balance it by putting more steps into dividing $$$n$$$ and less into dividing $$$x$$$. I figured a cube root might work so I went with $$$\lceil{x^{0.3333}\rceil}$$$ and that got (200005 for $$$n=200000$$$). 102597360

Just realised my 2 element approach is slightly different from what you describe. It's actually a 3 element approach in most cases. I leave 2,x and n. Then repeatedly divide n by x until I get 1 followed by dividing x by 2 until I get 1 (unless x=2).

Yeah, it's actually nice that the constraints deny the simplest ideas, like "leave 2 and n", but allow so many approaches to turn into actual solutions. Kudos again to the authors!

My solution to D with thought process:

* When you divide a smaller number by a bigger number you get

`1`

* Say

`arr = [1, 2,..., n]`

* When we do

`{i, n}`

operations for every`i`

, we get`[1, 1, 1..., n]`

* But we want 2 at the end...

* So, we will make operations

`{n, i}`

whenever we can.* Say we are at

`i`

(processing the numbers from n-1 to 1)I don't have a formal proof of this, but it is something on the lines of

`How many times do we square-root a number to get 2`

This is the code for above approach: 102649278

Here's my solution for problem

Aif we remove the constraint of there beingexactly one '(' and ')'. https://mirror.codeforces.com/contest/1469/submission/102634522Please let me know if there's anything wrong with the logic.

Nice contest! I recorded myself solving and explaining problems (only A-D today, so there is definitely a room for improvement), here is the YT link. Of course, there was a post-contest stream by Neal Wu with the discussion of the solutions, but maybe you will find my explanations useful as well.

I wanted to ask what is the meaning of

There is exactly one character ( and exactly one character )In the string there will be only one '(' opening bracket and only one ')' closing bracket.

like if length is 6 can you construct one test case for me ??

)????(, This could be one , another (???)? , You will have to use exactly one ( and exactly one ) , and remaining should be ?

What's the famous hack for E?

My guess is

Solutions using hashing forgetting to use srand which leads to fixed seed giving WA due to collisions

Using string set for hashing which is too slow

I hacked the solutions (including yours :P) where while checking the last 20 characters of the substring people forgot to check whether the remaining all characters of that substring are zero or not.

How did so many solutions pass 89 tests ?! Thanks for answering.

dorijanlendvaj is GOD!

the predictor says +43 for a account when the contest over,but +106 for that account right now.

Hope everyone won't FST >_<

How is it even rated for you?

He uses the ID delta_X to participate.

Hello, everyone!

I found one submission for problem E which used a

HASHalgorithm, can youhackit? In fact, I wonder how to hack suchHASHalgorithms. If you know the way to hack it, please contact with me, thanks so much!As I know, there is no good way now to hack hash algorithms that use multiple large prime numbers.

I also realized this problem after writing this comment some time.

Anyway, thanks a lot!

Unfortunately, the submission above which used a

HASHalgorithm has beenhacked.I think it's probably because he's always using the power of two.

How to solve E by SAM? :-(

If you flip all the numbers in the string, the problem is now to find the minimum string of size K that is not a substring of $$$S$$$. To do that, build the automaton of $$$S$$$ and just run a dfs trying to put a 0 first, and if that failed, try to put 1. If your path is already of length K, then this path is not valid (it is a substring of $$$S$$$). If at some moment, you try to put a digit and there is no edge labeled with that number going out from the current vertex of the automaton, you know that it's not a substring of $$$S$$$ anymore, so you just complete it with zeros and print it.

Time and memory complexity is $$$O(n)$$$. Here is my submission :)

Thanks for your reply! Now i know how to solve it. :-)

Could you please provide a tutorial for SAM or whatever you mean by building an "automaton of S"?

Thank you in advance.

This tutorial explains everything in a really nice way :)

Thank you!

How to approach A? I used stacks for it but got WA

If the length of the string is odd, it's not possible. If the first character is ) or the last character is (, it's not possible. Otherwise you can show a solution exists.

it's really sad to see people getting hacked on E, including me XD

My submission for E fails at test case 92. I'm going through masks and printing the one with the least value that doesn't correspond to the last min(k, 20) bits of any of the k-length inverted substrings. Any clues?

I do the same and also get WA in Test #92.

I found my mistake, I didn't consider the leading zeroes. even if your solution gives some mask (not all zeros), a string with all zeros can still be the answer, because it might match with its zeros before the last 20 characters.

Here's a test to reproduce the flaw:

Yes, you're right, I got it the next day. Thanks.

My AC submission

My first AK for Div.2 round. I am very happy. Thank you!

Sorry, got the statement my bad!For 1469A - Regular Bracket Sequence

In this problem (Edu Round 101- A) most people code doesn't consider below stated test case.

Can anyone explain why?

Test Case:

There is exactly one character ( and exactly one character ) in this sequence.Because the input should contain only one ( and only one ) brackets.

Why doesn't the system test start?

Magic moment

Do you want to increase your friends by putting this comment?I wanna increase your contribution! It's very cold and frosty!

I tried looking at the solutions of others in the hope to learn about problems I couldn't solve(as I thought was a reason for educational rounds), but in solutions, it is really hard to find java codes, does standing have some feature to find java solution codes in standings, or if not I hope they make such option.

For each problem, there's a "Solved" page (example: https://mirror.codeforces.com/contest/1469/status/A). Typically the solutions are ordered by size, which puts Java behind since it's verbose at times. But you can use the filter to the right, select "Verdict: Accepted" and "Language: Java 8" (or Java 11).

Hi ! Good job. When will the ratings change ?

Sometimes more than 5 hours after system testing

Thanks a lot !

When will the rate change take place ?

Next year

How long will it take to update the ratings?

2 more decades only.. XD

editorial please ?

When will the editorial come out? I believe there are many people waiting for it.

m

What is it about?

.

My solution 102607224 for question D has been marked for plagiarism with solutions manhar/102593123 and Mahipalkeizer/102619153.Our main code is completely different,the only common thing is fast input output code we used was available publicly through a blog before the start of the contest. The blog link is this

the corresponding github link reached through the blog is this

I request you to remove the plagiarism on it asap.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Could you tell me what's wrong with this submission? https://mirror.codeforces.com/contest/1469/submission/102750136 I can't see what 79 test case is about