Hello Codeforces!

On Feb/22/2022 17:35 (Moscow time) Educational Codeforces Round 123 (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, 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!

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

*Hey, Codeforces!*

*Once again, it is time for another exciting scholarship opportunity from Harbour.Space!*

*We have partnered with various tech companies to offer Bachelor’s or Master’s degree scholarships in Computer Science, Data Science, Cyber Security, and Front-end Development and work experience in the partnered companies.*

*We are looking for various junior to mid-level positions to fill in different fields such as:*

**Java Spring / Node.js Back-End Developer****DevOps Engineer****Kotlin Web App Developer****React / React Native Front-End Developer****Cyber Security Specialist**

**Requirements:**

*High School Diploma for Bachelor degree applicants or***Bachelor’s degree**for Master degree applicants*Professional fluency in***English****Previous experience**is a must for Master student applicants and a plus for Bachelor student applicants

*Make sure to apply before Mar 13, 2022, to be eligible for the scholarship and reduced application fee.*

*Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from students.*

*Good luck on your round, and see you next time!*

*Harbour.Space University*

**UPD:** Editorial is out

Hoping for a great contest. Good luck and high ratings for everyone.

Its great that cf is arranging two contest in two continuos days ;-;

Then there is google hashcode on 24. Man, this week is packed with excitement for programmers.

Glad to see MVL switching careers to CP and leaving Chess

Spoilerthe contest must have the palindrome problems.

Whylook at date

May all who deserve, gain

++ ∆SpoilerYupp, as u can see it's a Pre_increment delta OwO

I'm looking forward to this contest.

Monsters Incoming !

looks like the gap between E and F is too big...

How to solve E?

count the cells which must be missed.

After processing the first $$$i$$$ characters, lets suppose we are at some position $$${x, y}$$$ .

Assume wlog we have $$$s_{i} = D$$$.

We clearly can't even reach points with $$$x' \lt x$$$ or $$$y' \lt y$$$, so let's assume we've marked them as unreachable in the previous $$$i - 1$$$ steps.

If this is the last character, we can clearly reach all points with $$$x' \geq x$$$ and $$$y' \geq y$$$, so we don't need to subtract anything. Otherwise we don't need to worry about points with $$$x' \gt x$$$, since the next position (which will be on row $$$x + 1$$$ since $$$s_{i} = D$$$) is better suited to that task since any repetition from that point will use the same sequence of repetitions, except for one less downward step.

So that leaves the points to the right on the same row. If the character $$$R$$$, appears $$$k$$$ more times after position $$$i$$$ of the string, then we will go out of the grid trying to access the last $$$k$$$ columns of this row, so they are unreachable. The rest can clearly be reached by repeating the last occurrence of $$$R$$$ before position $$$i$$$.

So we just need to subtract $$$k$$$ from the answer at this position. Any further position is in a lower row so we won't overcount.

We can see due to symmetry the same holds for $$$s_i = R$$$ with $$$D$$$ occuring $$$k$$$ more times after position $$$i$$$.

One last thing to be careful about, is that for the first substring of equal characters, there is no character to move us downward / right to reach those cells perpendicular to our direction of motion, so we always have to subtract $$$n - 1$$$ in that case.

Solution — 147333480

Got AC using your approach. Thanks for sharing.

Solution

I'm curious how many others just kept randomly shuffling the permutation till they got one that was anti-fibonnaci in B lol.

Did one of them actually passed the system tests ?

Yeah mine did.

using shuffle() instead of next_permutation() did pass

It reasonably should, I intuitively feel that the probability of selecting an anti-fibonnaci is either $$$\frac{1}{c}$$$ for some small constant $$$c$$$ or at worst $$$\frac{1}{n}$$$, both of which will easily pass.

I still ran the max case ($$$T = 48$$$, $$$n = 50$$$) and it passed in $$$15$$$ ms.

I just reversed the first half and second half for every partition at index (1,n)

C harder than D and E

Once you know the solution, you will facepalm. I figured it out after spending more then an hour and ha half and it's soo simple I was overcomplicated it. Wasted D tho :(

Same thing happened with me..C is basically dp with kadane's algo i have wasted all my time doing C

It can easily be solved without kadane's

Just naming a container as dp doesn't make the solution be a dp solution!

i'm so frustrated. why did i stop extending left/right when there's a negative number... certified facepalm, didn't make it in time

I did something similar but in D. Instead of multiplying k I was adding k to the answer... certified facepalm.

Once you figure out its DP, it becomes easy.

DP[i][j] — max continous subarray sum upto the ith index in array and j addition of X.

speeeeed forces. didn't expect this :(

How to solve F?

Could someone take a look at why my O(N) solution for D is failing with a TLE? Code here

Look carefully at the constraints on $$$n$$$ and $$$m$$$

SpoilerYour complexity is $$$O(t*n)$$$ due to creating vectors for every test case.

n & m can be large per testcase you can use set instead.

Logic for C?

First, we will calculate the max sum for each subarray for length i=0,n, We can do this just by 2 simple FOR loops. So now we have an array SubArraySum[], and subArraySum[i] represents the max sum among the ith length subArray. Now to find the best answer when we can add some k elements of value x, we can do this by iterating over the subArraySum array, and for a SubArray of length =i we can increase its value by x*min(k,i).

Thank you now i got the 3rd problem

Thanks! Enjoyed the problems, however, don't you guys feel like the difficulty gap between CF div2 rounds and edus has become large? Or is it just me who's good at such problems and it's meant to be this way? Somehow my performance in edus (well, last two) is exponentially better than in normal div2s and i dont remember edus being so friendly even a little while back.

~~i feel one could exploit edus for large rating gains <doublestrike> like i did </doublestrike>.~~I've observed the same thing recently, with EDUs being ridiculously free :thinking:

I agree, although I feel like this contest in particular was pretty easy even for an EDU.

finally a good contest :)

Could someone tell me why my solution is giving TLE for question D link-https://codeforces.com/contest/1644/submission/147348233

you are creating vectors inside the test case loop, n,m can be upto 2e5. doing this vector creation of this much size t(testcases) time, leads to TLE. To solve this you need to create the vectors outside the test case loop and set and unset it

Can anyone please tell why my code is getting TLE on testcase 6 in ques D.. Acc to me is O(N) solution.As I couldn't find the reason in contest and after it also. My code https://codeforces.com/contest/1644/submission/147349933

It does not guarantee that the sum of M and N is within the 1e5 range.

But my code run on O(q) time so why does it depend on n and m. Can you please elaborate or I am missing something??

Got it.Thankyou

The problem is declaring again and again those 3 vectors, because of n and m being up to 2e5 every time, it takes a lot of time to always fill the vectors. A simple replacement of those with a map and declaring one of them global will do the trick (Of course, with .clear() before each testcase). Here is your solution but modified as said above : https://codeforces.com/contest/1644/submission/147351646

Thankyou now i got it

got the logic of d, but not able to implement how to check two cell visited previous or not?

Process queries in reverse order. Then for any query q, check if either you have seen the row and the column of this query before (in which case this query shouldn't be counted), or if all the rows or all the columns have been painted already (again, in which case this query shouldn't be counted).

Now we know all queries that should be counted (call them valid_queries), the answer is simply $$$k^{validqueries}$$$.

https://codeforces.com/contest/1644/submission/147343490

can u please elaborate the logic behind processing queries in reverse order?

For any element r,c, we need to know whether it was painted over completely later (in which case its not a valid query and we don't consider it). It's easier to find this out if we reverse the queries, since at any point we have state of all painted cells so far, and can check if current query paints any new cells or not.

ok got it, thanks

Why is my solution 147366362, which is conceptually identical to your solution, TLE'ing? I've tried replacing

`long long`

with`int`

to no avail.Issue was using

`find(set.begin(), set.end(), value)`

rather than`set.find(value)`

. Apparently this makes a difference.Yeah , first one is O(N) , where as second one is O(logN) , where N is number of elements in set.

I guessed the algorithm, but I can't calculate it. :(

A — D, were great (didn't read E or F yet).

It's a pity I didn't read D thoroughly and was thinking about a way harder problem (one in which we're not given coordinates of operations — just q)

wait, what problem were you thinking about exactly lol? cus the answer changes depending on the coordinates xD

Version in which no coordinates are given.

Just n, m, q and k in input, nothing more.

But I couldn't really figure it out.

oh I think I understand, you're trying to maximize the number of colorings among all possible queries?

Yes.

What is the number of possible distinct colorings if you know grid is n x m, there are k colors and you know that q coloring operations were performed (but you don't know anything about those operations).

oh my bad LOL, I just realized that what you originally said made sense, I sort of forgot the problem tbh xD

At the beginning I thought that I can change the order of q operations

I solved 2 Questions. I see no rating increase in my profile.Reason being???

Rating changes are not immediate

how many days it take??can you explain me everything about rating system??

How long rating changes takes

for more info read this blog post

Thoroughly enjoyed A through D. Wish I had more time to read the rest

any hints on how to do B ques?

The first permutation is n,n-1,...,1. Let's say this is (1).

Then just swap every adjacent pair of (1). There are n-1 adjacent pairs so you will get total n pairs.

Let's understand this with an example of n=4.

1: 4 3 2 1

2: 3 4 2 1

3: 4 2 3 1

4: 4 3 1 2

you may think about how to construct an answer for $$$n$$$ when an answer for $$$n-1$$$ is known.

Sort the permutation in descending order and shift the smallest element (i.e 1) one place at a time from right to left. For example if n=4:

`4->3->2->1`

,`4->3->1->2`

,`4->1->3->2`

,`1->4->3->2`

Can Someone mention a testcase where my submission for C is failing. Submission: Link to Code

Failing testcase: Ticket 485

To users who get Time Limit exceeded at test 6 of problem D (like me, spend almost half an hour to figure it out)

You should not initiate the rows = [-1]*n and cols = [-1]*m, because it is not guaranteed that the sum of m or n do not exceed 2*10^5. You should using dictionary or hashmap instead.

And thanks for testers for setting test case 6, or I will definitely get hacked after the contest.

me getting hacked after passing test case 6 in 1996 ms ,used normal map xD

If you are/were getting a

WA/REverdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.comProblems added: "A, B, C, D, E, F".

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the

contest_id,problem_indexandsubmission_id.who solved C without dp?

I used a segment tree.

Mine segtree tled twice smh

I got MLE twice until I found I only need to keep one (optimal) value for each length...

turns out we don't need a segment tree, some suffix max works.

i think i did without dp, though after the contest

You can just find the max sum for each subsegment for a fixed size for all sizes from 1 to n. and then just try all values of max with given k

my implementation.

CodeMe, well don't exactly know if it would be called as DP or not, but there was a little bit of pre-calculation for calculating the maximum possible sums of each of subarrays and then finally iterating over them to get optimal answer for each k from 0 to n.

vector mxsum(n+1,INT_MIN);

I can't understand why in Problem F the constraint is $$$1 \le n,k \le 2*10^5$$$.

Is the key point of the problem how to calculate Stirling numbers using NTT?

Absolutely this problem should focus on how to find the solution, not how to use polynomial.

This wastes me too much time so I can't solve it in contest.

I was not able to solve it in time either(cause stupid me thought it was impossible to calculate the sum of Stirling numbers fast enough). But since I hate NTT and I like this problem I have upsolved it without NTT in O(n * sqrt(n))147355537

After some optimizations(147356152) it is now running in 1,5 seconds, wich is 1/4 of TL, so maybe this solution is actually intendent

Will you please explain it ?

1) I've just realized I am damn and solved this problem in O(nlog)(147475186)

2) My solution is almost same as in the editorial, but I compute ans = sum S(i,1)+S(i,2)..+S(i,k) in O(min(i,k)) with no fft or other techniques. Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have:

S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ). Let d = j-t, then

ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed

i cant even understand the question D, i solved the answer for no of uniques after all operations, my brain found this sub problem easier and got attached to it, soo much more to learn

Spoiler... There is a case in which every row colored from bottom to top, so you can't take more elements, same for columns.

thanks but i knew that i just was confused about the question itself

Implementation forces

anyone else who did random shuffle in B :)

123 people did random shuffle in B

which n gives the highest chances for hacking? :D

Can Someone give small hints for Problem E.

Make sure to not spoil it for other people.

SpoilerRectangles

Could someone take a look at why my O(N) solution for D is failing with a TLE? Neon

`https://codeforces.com/contest/1644/submission/147331915`

Your solution is exactly $$$O(nT)$$$, and there isn't any constrant on $$$\sum n$$$.

The hacker generated a testdata with $$$t = 10000, n = m = k = 2\times 10^5, q = 20$$$ to maximize $$$\sum n$$$.

GOT IT

I used boolean vector of size n and m instead of integer vector and the code is not getting TLE on the pretests, so I would like to know exactly how fast is the initialization of boolean vector as compared to integer vector? (Submission link: https://codeforces.com/contest/1644/submission/147329366)

Maybe there is some mysterious optimization in the implementation of

`std::vector`

. In fact I don't know, either.std::vector is something like bitmap, which is at least 8 times faster than normal version (I guess).

How to solve D ???

process from back, keep track of used rows and columns.

Main idea is that some rows and columns get completely overlapped in operations succeding it, making that operation worthless. So just count those out, then, k ^ cnt

For video explanation you can check out my video

ConstraintForces

I don't think it's reasonable that there weren't constraints on $$$\sum n$$$ and $$$\sum m$$$. Some people (including me) used O(nT) initialization in each testcase, and some of them got hacked, some didn't.

My submission ran about 1300ms so it can't be hacked due to its relatively small constant, but some submissions that ran 1900+ms got hacked because of the fluctuation of the judge.

I don't think it is constant that matters in Codeforces contest. Maybe a TL of 1000ms is more preferable for C++.

Why is my O(q) approach giving tle for d?

https://codeforces.com/contest/1644/submission/147345716

Because you are Initializing row and col vectors for each testcase, which takes O(nT) and since there weren't any constraints on ∑n and ∑m, it should TLE.

There is no constraint on sum of n and m in problem

so you can have $$$t * (n + m) = 10^4 * 4 * 10^5 = 4 * 10^9$$$ operations in your code

Did anyone else do a 2-D Dp for C?

solving E 3 minutes after contest finished is really big pain

it's also pain to have >40min for F but can't even get any clue

how would u rate b,c problems ?

B — 1200 C — 1400

I think it was a good round.

But it has only ~100 likes.

Didnt like C(too straightforward, no interesting idea), B and D was good though.

Any hint for E

Thanks for the round!I liked the tasks and they were interesting!

Was stuck in C for quite some time. Dropping by few hints for whosoever interested

Hint 1Find max sum of subarrays of length 1 to n

Hint 2Add x to as many distinct elements you can in max sum subarray

Hint 3Find maximum of 0 and the values obtained

Can someone tell me why my solution 147364129 for problem D is getting WA?

Hint:Does the order of queries matters?

Can someone explain why do I see this contest as unrated?

The rating hasn't yet been recalculated

I am waiting to see what happens if the ratings for this round are not updated before the Div1/Div2 round starts xD

it would be more funny if someone registered for div2 with rating<2100 will get delta above it for previous contest after joining next contest :)

Codeforces right now:Just 6 to 7 mins before the next round, the ratings got updated.

That was close. Looks like we'll never know.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Is there any specific reason why ratings of Educational rounds are delayed to update?

147328156

Can someone help me figure out where my solution is wrong ? Please , Thank you !! (Problem C)

My god, i just took inf as -1e8 & taking it as < -1e14 , would do the trick , just because the sum can go below -1e8, feelsbadman :(

Huge gap between E and F. XD

hi, all my solutions got skipped on this round because code c is similar for other's code there must be a coincidence i didn't cheat or use other account to submit my solutions it's basic dp on best sum for len of k how can i speak to someone can help

what should i do ?

Why the difficulty rating of the problems havent been updated yet ?

The apply now link isn't working