Hello Codeforces!

On Jul/27/2023 17:35 (Moscow time) Educational Codeforces Round 152 (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 Adilbek adedalic Dalabaev, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

**WORK & STUDY OPPORTUNITY IN BARCELONA @HARBOUR.SPACE UNIVERSITY**

*Harbour.Space University has partnered with Giga (Unicef) to offer Bachelor's and Master’s degree scholarships in the fields of Data Science, Computer Science and Front-end Development as well as work experience.*

*We are looking for various junior to mid level candidates:*

**Data Scientist:**

*Strong ML knowledge**Experience with Data Visualization Tools like matplotlib, ggplot, d3.js., Tableau that help to visually encode data**Excellent Communication Skills – it is incredibly important to describe findings to a technical and non-technical audience.**Strong Software Engineering Background**Hands-on experience with data science tools**Problem-solving aptitude**Analytical mind and great business sense**Degree in Computer Science, Engineering or relevant field is preferred*

**Data Analyst:**

*Cleansing and preparing data**Analyzing and exploring data**Expertise in statistics**Analyzing and visualizing data**Reports and dashboards**Communication and writing**Expertise in the domain**Solution-oriented*

**Front-end Developer:**

*This student will work closely with the blockchain developer and product lead to contribute to the design and implementation of user interfaces for the company's blockchain-based prototypes. They will be responsible for translating UI/UX design wireframes into functional and visually appealing web applications, ensuring seamless user experiences. The student will collaborate with blockchain and backend developers and designers to integrate front-end components with server-side logic and optimize application performance. They will also be involved in testing, debugging, and maintaining the front-end codebase. The intern will have the opportunity to gain practical experience in front-end development within the context of blockchain technology and contribute to the Giga’s mission of connecting schools to the internet.*

*Solid understanding of HTML, CSS, and JavaScript**Familiarity with front-end frameworks and tools such as React or Vue.js.**Strong problem-solving skills, attention to detail, and a passion for creating intuitive user interfaces are essential*

**Full Stack Developer:**

*Interest and experience in web application development, data products and OpenAPIs**Comfortable with on-cloud deployment services (preferably Azure), Git and CI/CD pipeline and deployment processes**Experience with open-source projects is highly preferred*

*All successful applicants will be eligible for a 100% tuition fee scholarship (29.900 €/year) provided by the partner company.*

**CANDIDATE’S COMMITMENT**

**Study Commitment:** *3 hours/day*

*You will complete 15 modules (each three weeks long) in one year. Daily class workload is 3 hours, plus homework to complete in your own time.*

**Work Commitment:** 4+ hours/day

*Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.*

**REQUIREMENTS:**

*Industry experience**International exposure**Eager to learn**Sustainability is a key topic for you**You want to work for an NGO*

**UPD:** The editorial has been published.

In the post title (рейтинговый для == Rated for), It seems that the Russian words is rather long.. lol:)

Fixed, thank you

Рейтинговый для the participants, this is genialno

Sorry, I don't understand what you're talking about. Could you show me where this phrase is used?

Let's take some education from Educational :)

I think I will be educated by Educational Round :(

I think I am,too.

orz

Hoping to cross 1300 mark

me too

I am the coolest and the bestest ^^

i think it will cool contest =)

I'm really looking forward to today's game.

Hope I can become candidate master today!

good luck

What do u do bro? Ur 2nd id?

monster

Another chance for solving interesting problems

Hope problem statements will be as short as blog.

The blog is not short anymore :D

It was short when i had posted comment ):

could smbd tell me, what does "orz" mean?

It's just like a man Kneel in worship of someone

well, then i dont understand why to write it hmm... ABOUT EVERYWHERE "stranger things"

Thank you for this contest :)

hope I can be a master

kinda random but can anyone help me https://codeforces.com/contest/469/submission/215875468 why this solution is not tle

Why do you think it should be TLE? Is there any particular reason?

I was confused i thought i could have 50000 elements not just 1000 elements.

Because constraints are low

Yes, thnx

I am going to have my first Div.2 round!!!

I have 185 points to Candidate Master. Good Luck. Hope to get more rating.

WA on 2 forces :/

and speedforces

Hello, Someone logged into my account, I recieved a message about an hour ago but I just noticed, it was not me I just changed the password. Please don't mistake this for cheating, they might have copied my code.

is this round rated for Div.1 as they are appearing in the official standings list?

Problems are good, I like them. But unfortunately, I didn't solve the problem E. Can someone provide a solution to the problem E?

Solution

It seems that my solution for F is an overkill (wow, this never happened before on ERs, right?..), so I would like the participants that solved it to share their approaches. The one approach I'm most interested in is binary search with building an implicit graph and checking that it's bipartite: I had a similar idea when I designed the problem, but the details of handling that graph were a big mess, so I decided to go with a completely different approach. How to check that the cost of the partition is $$$\ge m$$$ easily?

The main observation is that if $$$x<y<z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$. Proof: Define $$$f_i(n)$$$ to be the $$$i$$$-th bit of $$$n$$$. Let $$$i$$$ be the most significant bit of $$$x\oplus z$$$, then every bit higher than the $$$i$$$-th bit of $$$x,y,z$$$ must be equal, and $$$f_i(x)=0$$$, $$$f_i(z)=1$$$. If $$$f_i(y)=0$$$ then $$$x\oplus y<x\oplus z$$$, otherwise $$$y\oplus z<x\oplus z$$$.

Using this idea, we can prove that if $$$b_1<b_2<b_3<b_4<b_5$$$, then the edge between $$$b_1$$$ and $$$b_5$$$ are useless, because if we have this edge, we already have a triangle ($$$b_1,b_2,b_3$$$ or $$$b_3,b_4,b_5$$$). So there are only $$$O(n)$$$ useful edges.

I tried using a bit trie to do the binary search. Suppose you want >= m, then you can build the graph implicitly by doing the following bfs. You take a current node u, and then use your bittrie to take all values arr[x] such that arr[u]&arr[x] < m, then remove those x you used and add them to your queue. In this way you will prevent n^2 edges and get an implicit forest. Now that you have 2 different partitions, and check your check both of them to make sure their minxor >= m. At first, I tried using a bitTrie to do the checking as well but that TLEs, turns out the approach of sorting and checking adjacent elements as pointed out above will make it fast enough to pass. Also, I had to do alot of constant optimisation to make it work (recursive calls are too slow and pointer based bit trie is also too slow)

Submission: https://codeforces.com/contest/1849/submission/215997707

I have this approach too, but it runs in < 2 seconds and i only made one optimization from my previous TLE solution

216109677

Building the trie once is sufficient for all calls to check() since when you process node x, it is sufficient to find the logA important nodes of the trie which are the opposite color and mark them so you don't process them again. But since all you do in a check function is "remove" elements of a from the trie the first build is sufficient — just reset marked nodes for each call to check().

This is what I did.

First observation $$$x < y < z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$

Let's binary search on the maximum possible value.

So the problem reduces to checking whether a possible partition exists with the cost of both sets $$$\ge M$$$?

Iterate nos in sorted order. $$$dp[i][j]$$$ is true if it is possible to partition $$$a[1....i]$$$ (where $$$j<i$$$) such that the largest element in one set is at index $$$i$$$ and the largest element in other set is at index $$$j$$$, and false otherwise.

We can remove one dimension from this dp, letting $$$dp2[i]$$$ denote the smallest possible $$$j$$$, such that $$$dp[i][j]$$$ is true.

Once we know $$$dp2[i]$$$. $$$dp2[i+1]$$$ is either equal to $$$i$$$ or $$$dp2[i]$$$. So I first checked if it is possible to assign $$$dp2[i+1] = dp2[i]$$$, then I checked if $$$dp2[i+1]=i$$$, otherwise returned it is impossible to create such a partition.

ProofYOLO :')

The generalized version of this problem: https://codeforces.com/group/Uo1lq8ZyWf/contest/369641/problem/C

My solution does not construct a graph, but I guess it's one of the easiest for this problem.

Let's try to check if the 29-th bit is "on" in the answer. One can see that this can hold only if $$$n$$$ is not greater than 4. If $$$n$$$ is greater than 4, then it means that there're atleast 3 numbers whose 29-th bit is on/off, but number of groups is only 2 => their xor will be smaller than $$$2^{29}$$$.

If $$$n$$$ is not greater than 4, you can easily write a brute force and choose the best option. Otherwise, the answer is smaller than $$$2^{29}$$$. Let's notice that if 29-th bit is "on" in $$$x$$$ and isn't in $$$y$$$, then $$$x \oplus y$$$ is not smaller than $$$2^{29}$$$.

After this obsevation you can easily come up with the full solution: if $$$n$$$ is not greater than 4, then write a brute force. Otherwise, solve recursievly for number's whose (29, 28, 27..)-th bit is on/off.

CodeThe problems are nice, but horrible samples and queue issues

Had to wait a few minutes after each submission just to see WA on test 2.

The problems were good. It made me use my brain!!

I felt D was easier than A, didn't try B, C

I think the authors did a great job, I'm very fond of the problem set.

Is C solvable with polynomial string hashing? Comparing at most $$$m = 2 \cdot 10^5$$$ hashes by storing them in a set doesn't seem as an unreasonable approach.

Yeah. Submission

Just use two hashes. "If hash isn't working, it's because you haven't done enough of them"

I only now realized there is a 12 hour hacking phase. Well, feel free to hack this :(

I also used hashing, with $$$h(s) = \sum_{i=0}^{n-1} 2^i \cdot s_i$$$.

Even if my hash function is terrible, my out $$$\leq$$$ actual answer, but it fails while giving the output $$$=$$$ actual $$$+1$$$.

this is my submission.

Collisions in this problem will decrease the answer, since two different strings may be mapped into one value. However, there are other problems with your implementation, mainly on this line:

`hash = (h[l - 1] + h[n] - h[r] + (mod2[r] - mod2[r - c]) + mod) % mod;`

Here, I see two problems:

using int may result in an overflow inside the paranthesis (which in this case I expected to produce two values for the same string, and your ans should be $$$>$$$ the real ans).

whats inside the parenthesis could be, for example, $$$0 + 0 - 1 + (0 - 1e9+7) + (1e9+7) = -1$$$ and when you take mod, since $$$-1 \,\,(\textrm{mod}\, 1e9 + 7) \,= -1$$$, not $$$1e9 + 6$$$ (using the standard % operation)

Fixing these two issues (submission) gives WA on Test 4. This test consists of a string of size 2e5. Since the real answer is $$$136468$$$, the expected number of collisions will be approx. $$$\frac{136468^2}{2 \times 10^9} \approx 9$$$. Thus, the answer we get, $$$136460$$$, seems reasonable.

We could also use ull ($$$2^{64}$$$ mod) hashing, it could easily be broken, although I suspect the setters didn't bother creating a testcase to break it.

Damn! should have moded carefully

And hence the statement

Thanks man

just notice that if you have a pair {l,r}, this gives same as {l, r+1} if s[r+1] = 1, and this gives same as {l-1,r} if s[l-1] = 0.

so you just take each pair, remove all the extra ones on right side and zeros on left side and put in set, and output set.size(). you also have to add 1 if there is a pair that doesn't change s.

it is clear that this is sufficient, because if two pairs {l,r} are different after having removed the extra 1s and 0s, they will create different strings when sort.

you have to use a set.upper_bound or something to quickly remove extra 1s and zeros otherwise it will TLE because n*m = 10^11

@piaolianggg

why I have to add 1 if there is a pair that doesn't change s please..?

how to solve E? I overkilled it with 3 segment trees and binary lifting lol, didnt manage to finish implementing during contest, can smb slease tell a normal solution?)

See here for a relatively simple D&C solution. It can also be optimized to $$$O(n)$$$.

thank you!

The main observation is: let L[i] be the last index in prefix i that p[L[i]] > p[i] and R[i] be the first index in suffix i that p[R[i]] > p[i]. Then Sum for all i min(i — L[i], R[i] — i) is O(N log N).

Could you explain it in more detail?

This problem is literally the same!? (Actually it's easier due to the limitation of n) Is this allowed to have duplicate problems in Edu rounds OR duplicate problems from other sites or olympiads? I searched but couldn't find anything about this.

I guess it's just a coincidence. The statement is short, so it's not surprising it many people come up with that statement independently.

Well-balanced contest, thank you! Why there is too small memory limit in problem E? I've got ML with sparse and rewrote to segtree. But anyway, E is pretty good :)

Agree. Had to optimize binary lifting up to linear memory

Can you write your approach also? That will be of great help.

Odd, stable worked just fine for me

from problem C

is this approach accepted?

store prefix and suffix of given input string

store number of 1s and number of 0s of all the prefixes

create two vectors v0 and v1 such that v0[i] represents no of 0s and v1[i] represent no of 1s

ex:v0[3]="000" v1[5]="11111"

for given l and r can we create a new string like

pre[l-1]+v0[n0]+v1[n1]+suff[r+1]

where n0 and n1 are number of 0s and 1s in the range [l,r]

using all above data i did but i was getting memory limit exceeded

is this correct?

How you stored suffix?

i guess u need rolling hash to counter MLE

How to solve C.

I got wrong answer 2.

Can anyone tell me what should I correct

Here is my submission

Is my approach correct?

based off the wrong test case number which i also got it might be that you didnt account that the original string only counts if its duplicated at least once, i havent understood your idea though

You should not insert the original string at the beginning. You can only count it if some copy is same as the original string after the sorting operation. Anyway, you are sorting the range for each copy and there could be

`2*10^5`

of them. So, in worst case the complexity would be`O(n*m) ~ 10^10`

. That means, even if you fix the issue, you will likely get TLE.editorial?

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

why dp doesn't work on D?

my submission https://codeforces.com/contest/1849/submission/215977499

there will be at most 1.6*(10^6) operations

I too used DP. Here's my accepted solution : https://codeforces.com/contest/1849/submission/215947065

I think because of my recursive dp I got TLE

I also used recursive dp. My accepted solution link: https://codeforces.com/contest/1849/submission/215963313

It's because you forgot to cache some of the states.

SpoilerHere is the modified solution which is accepted: 216067849

Oh god Nothing can be worse than this

Thanks for debugging my code

Got stuck on B but it was interesting to me.. -ve delta for sure this round :(

for me also

From last few contests I am getting stuck on A or B

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

where can i read editorials for this contest?

What was solution for B?

reduce everything to equal or less than k, then use sorting or heap.

Thank you. I was using that idea during contest but just realised that i was getting WA for a mistaken symbol '<'

Seems like the trick in F has appeared quite a lot times recently, e.g. abc308g and 1851F. So it may seem more solvable for me than E...

+123 Delta in Recent Div.3 Contest and -121 Expected Delta in this Contest

My 2 pointer approach failed in D :( 215981454

Take a look at Ticket 17010 from

CF Stressfor a counter example.How to solve C questions. Every time I can manage to finish 2 questions but can't go to the next

Hashing

It was already explained by few folks in the comment section. However, I would like to share my approach. Let's say you have a range

[l,r]. Let's consider a functionS(l,r)which returns a string after sorting the range[l, r]on a copy of the original strings.S(l,r+1) = S(l, r)only ifs[r+1] = 1. Similarly,S(l-1, r) = S(l, r)only ifs[l-1] = 0. We can extend it further toS(l-a, r+b) = S(l, r)only ifs[l-a...l-1] = 0ands[r+1...r+b] = 1. Now, for each range, find the pair(a, b)whereS(l, r) = S(l-a, r+b),ais minimised, andbis maximised. Then insert the pair into a set. The output would be the size of the set. However, you need to handle the cases whereS(l,r)returns the original string. I guess if you understand the above approach, you would be able to figure that out easily.SpoilerMy AC Submission: 216065217

Thanks a lot

Problem A — Greedy + Implementation

Problem B — Greedy + Implementation

Problem C — Greedy + Implementation

Problem D — Greedy + Implementation

C wasn't really greedy (it was precomputation using datastructures e.g. an array so that you could answer each query in O(1)). I don't see how C involved the use of a greedy idea. And D could have been solved using DP, although the greedy D solution is more intuitive.

what is greedy for D?

my ac sollution here: https://codeforces.com/contest/1849/submission/216019392

First you compress the array. By this I mean if you have a contiguous subarray which only contains elements >= 1 then you compress it down to a single number which is the maximum number in the subarray. For example if the array was [0,0,1,1,1,0,1,2,1,1,0,1,2,0,1], I will compress it down to [0,0,1,0,2,0,2,0,1]. Now I spend coins on each position which isn't a 0, changing that position from blue to red. Notice that if the position is a 2 then both of its neighboring elements can also be changed from blue to red and if it is a 1 then only one of its neighbours can be changed from blue to red. I iterate through the array and if the current element is a 1, I first check if there is a neighbouring 0 to the left of it which is still blue. If there is, I change it to red. (This is the greedy idea to check the left neighbour first before the right neighbour as the left neighbour has no chance of being changed in the future so it is always optimal to change the left neighbouring 0 from blue to red if it's possible). If there isn't a neighbouring blue 0 on the left then I change the 0 to the right of the 1 to red instead of the one on the left. If I encounter a 2 while iterating then I just change both of its neighbouring 0s to red. After iterating, I then check how many 0s are still blue and spend coins individually on each one. Now the whole array is red.

thankss

Lets say there is a subarray 1 2 1 2 2 1 1 , coloring any 2 in the subarray will make it act like a single colored 2.

Similarly, if there is a subarray of continuous 1s, coloring any one will make the whole subarray act like a single colored 1.

So your answer would be no of subarrays of 1s and 2s counted above + the 0s which cannot be colored by any 1 or 2.

Submission Link — https://codeforces.com/contest/1849/submission/216052987

thanks

IMO, A is just simple math. I don't see how it fits to be a Greedy problem.

How to solve F?

Spent an hour and wasted 6 submissions on B because of tunnel vision. And then solved D 10 mins after contest. It was nice being cyan.

I also wasted my entire contest on B revolving around customized sorting of priority queue and ending up in TLE.

Btw, you can

`pq.push({a[i],n-i})`

so that standard pair order works.Can someone explain the DP solution for D?

It is not DP, it is purely Greedy.

First, we group all the continuous 1 and 2, and replace them with max.

For example, If the array is

[0, 1, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 1]

We can replace it with

[0, 2, 0, 1]

It is purely Greedy now, we take a

`covered`

array. We spend a coin for 2, and mark its adjacent as covered, then we check for 1.I know about the greedy solution but there are some people who have submitted a DP solution as well

Oh, okk. Below one has commented with DP code :D

215975523

Basically dp[i] is the minimum cost to color the first i elements, with three cases:

index i was colored by index i+1

index i is able to color index i+1 (i.e. a[i] > 0)

none of the above

Then you have to write 20 different transitions and hope that you haven't missed an edge case.

Thanks

Check my code I think it really is clear

what is parameter j?

it's a condition. $$$j=0$$$ means there is no condition. $$$j=1$$$ means that I can color the current index from the previous index. $$$j=2$$$ means that I want to color the previous index from my current index

I felt like D was quite easy, just a matter of implementing it properly. I kept doubting whether I had come up with the right approach since it seemed too easy and wasted time. Although it does have less solves than C, so there's that..

I agree.

Is there any way of reporting a cheater in CF? Like, a self-hack with a secondary account. I'm refering to this submission: 215982877 in the Educational Codeforces Round 152 (Rated for Div. 2)

The open hack phase does not give a rating, so its only kinda necessary to report him

How to solve c? Please give me hints

hint1think about first change from the left after sorting

hint2think about first change from the right after sorting

hint3will the middle elements differ for them ?

Imagine we have to sort substring [L, R]. Let P be the length of longest prefix, consisting of 0, and S be the length of longest suffix, consisting of 1. Then, we actually have to sort only substring [L + P, R — S] (notice, if L + P > R — S, then substring is already sorted). In other words, L + P and R — S are the leftmost and the rightmost positions, which will have opposite bit after sorting. So, we have to count the number of distinct segments [L + P, R — S].

P.S. Sorry, if my English hurts you

Thank you

Why won't you die?

Hint 1Think what will happen if we store only larger version of the subarray.Larger version here means maximum index on either side that is continuous.

Hint 2For example you are told to sort [2,4] subarray, Instead of storing only [2,4] store [maximum index to the left that gives you zero(if there is zero), maximum index to the right that gives you one(if there is one)]

Final code.I have written redundant code in the middle which can be made into a function. 215981777

If you like please upvote.

in problem b i tried using priority queue but got tle,can anyone help me with that,https://codeforces.com/contest/1849/submission/215983479

think about case where k = 1 and all health of monsters are 1e9, then it is O(n * logn * 1e9) that's pretty slow

array elements are upto 10^9 so if k = 1 then your solution takes upto n * 10^9 operations for single test, in other words TLE.

In case

`k = 1`

and some`a[i] = 1e9`

then it's easy for your solution to get TLE.Notice that you can subtract every a[i]the same multiple of k until one the a[i] reaches 0. Observe that the final array b where b[i] <= 0 for all i is given by b[i] = a[i]%k — bool(a[i]%k > 0)*k. By sorting b in decreasing fashion, you obtain the order of elimination (you can use a custom sort with a vector of pairs to keep track of the index).

I got stuck on problem B because I don't know C++ STL very well and don't know how to use a pair. Sadge, but the contest was educational.

getting tle in problem B using priority queue and i thought complexity is in o(n log n) only

No. If you use priority queue the complexity will be O(n * log(n) * 10^9) so it is too slow

You can think about getting remainder

same approach but my submission was accepted, i used heap in python

Can someone find an issue with my solution? I am getting TLE using priority queue.

I used binary search find the multiple of k I need to subtract if the top element is too large but still TLE.

Small step k can brick your solution.

can C be solved using binary search on prefix sum??

Problem E. I wrote a double pointer method.

The idea is to take the 1-n enumerator as the minimum value of Subsequence like the ruler method. Obviously, there is a range, that is, double pointers. But the complexity is strange. I want to seek help to prove its complexity. I also hope that everyone can come and hack more often. thx

the code

Found the problem, thank you for SpaceJellyfish hacking me. The problem lies in n, 1, n-1,2, n-2,3 Very smart

Can Someone give me some detailed approach on C...I was getting TLE from brute and seg Tree..

My approach:

Let's iterate through string S and remember indexes of 0's and 1's.

Now for every l and r binary search index of the first 1 and the last 0 in that range.

If the 0 index is lower than 1 index then there was no 'movement'.

Now insert pair {idx1, idx0} to the set.

The answer is set.size() + 1 if the string stayed the same.

Code

gotcha

thank you, I wanted to know the solution for this problem very much

hi woonder

can you explain why we should add this code in your solution

if (ans0 < ans1) st.insert({ 0, 0 }); thanks in advance

ans0 = index of the leftmost 0 in the given range

ans1 = index of the rightmost 1 in the given range

if ans0 < ans1 then string won't change.

So I just add {0, 0} to the set and then I don't need to add 1 to the answer at the end.

I hope I helped.

YES !

THANK YOU for reply

I got it thanks alot

Here is my comment to similar question.

SpoilerLink to the comment

Thank you for this contest! The problems were fun and enjoyable, and statements were short. I guess C was a little difficult and D was easy, but that's not too bad. This was also my first time AK'ing in Div.2. I'd say this was one of the best Div.2's in a while.

Hashing approach for C:

First calculate hash value of the initial string. Now if we apply the operation in range $$$[l,r]$$$ then the hash value of segment $$$[1,l-1]$$$ and $$$[r+1,n]$$$ will remain the same. Let there be $$$x$$$ number of zeros and $$$y$$$ number of ones in segment $$$[l,r]$$$ and the base used for hashing be $$$p$$$. let $$$x=3, y=4$$$. So, after the operation the new hash value will be:

$$$($$$hash value of segment $$$[1,l-1])$$$ $$$+$$$ $$$($$$hash value of "$$$000$$$" $$$\times p^{l})$$$ + $$$($$$hash value of "$$$1111$$$" $$$\times p^{l+x})$$$ + $$$($$$hash value of segment $$$[r+1,n])$$$

hash values for strings with all zeros and all ones can be pre-calculated.

store this new hash value in set. So answer will be size of the set.

My submission: 215990369

256127907 Can u please tell me what is wrong with this? It would be a great help!

How we can store the suffix of string efficiently?

For problem C:-

My idea was to store suffixes and prefixes of string and prefix count of one zero ..

And in query..just make string temp

Temp=PREFIX [L-1]+prefixOne+prefixZer+SUFFIX[R+1]

It gave me mle..

why my solution to problem B TLEs at TC 6? Someone pls help me...

i got it too, tho now i understood that suppose a[i] is of order 1e9 and k=1 (in simpler words a[i]>>k) , then to make a[i] to zero and then finally popping it out from priority queue will take time of a[i]-k which will be approx to 1e9 operations and yeah for popping and pushing consider logn as well so net complexity will be O(n*logn*(a[i]-k))

Here is my solution to E by using some binary search. The time complexity is $$$O(n(logn)^2)$$$ https://codeforces.com/contest/1849/submission/215980613

Can you explain your approach?

Is there any penalty for unsuccessful hacking attempts in this contest?

no

https://codeforces.com/contest/1849/submission/215999156

Can someone please help me to find error in my code for problem D

Take a look at Ticket 17009 from

CF Stressfor a counter example.Problem B was really cool!!!

could you help to understand problem b？

Ignore typos and pardon for being lateSome key points to notice - -- We can attack the monster who has max health points -- To kill a monster in a single attack(or damage) its health ability should be less than or equal to 'k' -- In case of same health ability, lower index must be attacked

So... we can make out that we only need the health ability of the monsters is so low that we can kill them by one attack and since we need to attack the monster with the higher ability first, the killing of the monsters will be in the descending order of the abilities, incase of similar ability in multiple monsters order of index will be followed to kill them.

Now the code part, the way to get the ability to kill the monsters in a single move is to just get remainder(%) of the ability to the damage(k). In some of the cases the remainder might be 0, which would mean that monster needed exactly 'k' damage to get killed and to make its ability 0, for such cases we will make it's value to 'k', since it is the needed damage to kill the monster.

Let's say, array was [ a, b, c, d], and all these abilities a,b,c,d are not divisible by 'k' then what we will need is [ a%k, b%k, c%k, d%k]. If any ability let's say, 'c' is divisible by 'k', then what we will need is [ a%k, b%k, k, d%k].

Notice the test case [2,8,3,5], the first monster can be killed when the array becomes [2,2,3,2](what we need), after that we can kill them one after the other...

-> https://codeforces.com/contest/1849/submission/216003321

What is the greedy solution for D?

Video Editorial for problem A,B,C and D.

https://youtu.be/LrroyicG0mg

For question C, I tried to use a hashmap to store the pairs after i modify them according to the nearest out of order character between the pair, where the right number is mapped to the first 1 on its left and the left number is mapped to the first 0 on its right. I use an array to store whats the nearest 1 on left and 0 on right for each doing a linear pass for each. I got a WA2, and my solution is attached here https://codeforces.com/contest/1849/submission/215973791. Is there anything wrong with my idea? Thanks for any help!

Take a look at Ticket 17008 from

CF Stressfor a counter example.thanks, i figured that i missed the bit where the original has to be duped to count

Please debug my code https://codeforces.com/contest/1849/submission/216006105

if x is 0 you need to make it equal to k

Thank You!!

I really like E and F, very good and educational problems!

## RIP

sir，could you help me to understand problem b?

Can u explain your dp solution of Problem D

## Remember to use long long

Here is my solution to E which runs in $$$O(n \log^2 n)$$$. Hack attempts are appreciated.

Hi,I am unable to find the mistake in my greedy approach for problem D. It is failing on test case 28. Can someone please help me.

Here is my solution to Problem D

I don't know where the mistake really is, but I found some hack cases.

In:

Out:

In:

Out:

The hack cases also works with n=8,10...

Thanks ,I found the mistake.

Nice hack, and I suppose your profile photo is Masaki in galgame Amairo islenauts produced by Yuzusoft...

wafu(

Xiaoxin Youzichu!

Below 2100...

Can anyone please help me out with problem C. Submission 1 Submission 2

according to me Submission 1 should not fail as there would only be valid answer between the range (first 1 and last 0) both inclusive but by removing this condition I got accepted. If someone could point my mistake where I am going wrong.

Sorry for such a bad implementation. Thanks in advance

Still looking for help!!!

This test case gives different outputs for your submissions. Notice how 2 7 still gives you a different sort, but the indices are both outside of the first 1 and last 0, which are 3 and 6

thanks didn't thought of this case got it accepted after adjusting the condition

Q3 and Q4 was easy but tricky

Why does my profile show that this contest is unrated? I'd become a specialist if they would increase my rating :(

for me as well.

contest ratings are distributed few hours after system tests

no the issue is it is showing under unrated contests.

have patience mate

Can someone tell what is mistake in my approach for problem 3. In this i used trie data structure to store every possible string. But, still i am getting WA in test case 2.please find the mistake in 216055609

When you are posting such a long piece of code, you need Spoiler and Block, which you can easily find up the textbox where you write your comments. It looks like:

My solution for Cthis is my solution for problem C btw.

In my opinion, you may fix your formatting first, otherwise it will be difficult for anyone to understand your code. Hope this helps.

please find the mistake in 216055609

Take a look at Ticket 17007 from

CF Stressfor a counter example.cool contest

Can anybody explain the dp solution of Problem D ( I know it can be solved using greedy)

Look at this comment.

Orz

still waiting for rating changes :_)

so long :<

How to solve E? pls help.

Spoiler: You can solve it using diramida to find first / last element which is more/less then x. Another spoiler: iterate the minimum from 1 to n

what is diramida

Sorry) I meant treap)) I thought that in english this data structure is called like this))

i tried to think in that direction, but seems difficult

First , for each element you can find the right most position that is more than a[i] using stack;(and find the right most position that is less than a[i]) Now lets define dp[l] = is position of max more than position of min in [l,r] for a fixed r: Now lets check how does dp[i] change after we increase r by 1; for all i such that a[r] is max in [i,r] , dp[i] will be changed to 1 , and in the same way for all i such that a[r] is min in [i,r] , dp[i] will be changed to 0;and the other dps will remain the same(because a[r] is not the max nor the min of that array so it will not affect dps condition); So sum of dp[i] for a fixed r will be the number of segments that we should count that the segment ends at r So for solving this problem we can increase r 1 by 1 and update dps using sum data structures like segment tree and we can solve this problem in O(n*log(n));

Imagine two stacks: one for increasing elements, the other for decreasing elements. If you draw it, you get a diagram of points consisting of two lines (one for increasing, one for decreasing). Then, for each point in the decreasing line, connect it to the first point smaller or equal to itself. The answer for a single index $$$i$$$ is the sum of the lengths of such segments. In order to maintain it while going left-to-right, use two sets with two stacks.

Code: https://codeforces.com/contest/1849/submission/216019848.

will the rating still change later? qwq

Where can I find editorial?

https://codeforces.com/blog/entry/118752

Can someone expalin the segment tree approach of problem E.

Why is the rating not updated yet?

For problem E, I did

divide and conquer, maintained prefix and suffix max and min values, and did 2 pointer kind of approach.Let's say I want to calculate $$$Ans(L, R)$$$ using divide and conquer. (L, R both inclusive) we can see that

$$$Ans(L, R) = Ans(L, mid) + Ans(mid+1, R) + X$$$

where $$$X$$$ is the count of valid subarrays whose left pointer in the left region $$$(L, mid)$$$ and right pointer in the right region $$$(mid+1, R)$$$.

To count this $$$X$$$, we have the following cases:

Case 1) When both $$$max$$$ and $$$min$$$ are in the left half.

Case 2) When both $$$max$$$ and $$$min$$$ are in the right half.

Case 3) When $$$min$$$ is in the left and $$$max$$$ is in the right half.

For working out all of the cases, it can be seen that fixing the $$$i$$$ pointer in the left/right subarray and finding the count of the valid $$$j$$$ pointer in the right/left subarray approach will work. It can further be optimized to a 2-pointer by observing that the $$$MAX$$$ value keeps increasing in the prefix, and the $$$MIN$$$ value keeps decreasing. And some recalculation can be made from previous value of $$$i$$$ pointer.

Each case mentioned above can be worked out in $$$O(N)$$$

Overall time complexity is $$$O(NlogN)$$$.

Code: https://codeforces.com/contest/1849/submission/216111032

It's my first time participating in an educational Codeforces round. It said, "This round will be

rated for the participants with rating lower than 2100". However it shows as unrated on my profile. Can someone please tell me it shows unrated?Hey, it's rated round, it takes some while sometimes to update ratings so hold on buddy :)

Ohh ok ok, thanks for clarifying.

Because it isn't rated YET

When will the ratings get updated?

why not still rated? lol

I hope rating changes will update before i get to sleep.

I'm excited for $$$myRating \ mod \ 10 = 0$$$

Why the rating is still not given for this contest

I hope rating changes will update before i get to sleep.standingsAre they including hash table hacks on the testcases? After the contest they added testcase 9 on B where I got TLE 216129676. By just changing the hashes I get AC 216106308. Should I always during contests avoid using sets and dicts with integers keys (Python)?

absolutely yes. all of the system testing point were came from the user’s hack point. when hacker view someone’s codes using hash and have some bugs, they will generate the unique point to make the AC to WA or other result.

In the TLE submission, this line

`pos[p].append(i+1)`

you can change to`pos[str(p)].append(i+1)`

and submit again.The editorial has been posted 3 hours ago and still there's no rating changes

Has it become unrated?

TLE on rating change! mike should find a better algorithm

could smbd help me: is it okay that my rating wasnt changed after this ed round?

yes

thx man

Is this round unrated? Someone answer please

finally rated lol

Slow tutorial :(

Can you teach me the DP method of D, how the state is designed, and how to transfer?

State --> For each index, maintain color(current color of the index), need(whether previous index need to be made red).

Transition --> Case 1: If need is active, current element must be >0. Case 2: If you choose to paint it red or if current element is red, check if you can make its adj element red as well. Case 3: If you leave it blue: if need is active, case 1 should be satisfied.

Could you explain the definition of $$$dp[i][0/1/2]$$$,and the meaning of transfer, thank you!

I used slightly different state. dp[color][need][index]. Iterating over each index, we have to make transition depending on current value of color and need. Try breaking down each cases, you will get the transitions. Here's my messy code if it might help. 216205936

Hello, please help me. I am trying to solve D but got the wrong answer on test case 28. Correcting my error would be very helpful for me.

my submission — SUBMISSION LINK

Thank you.

Take a look at Ticket 17006 from

CF Stressfor a counter example.Thank you very much brother. It helped me. Love you man.