Hello Codeforces!

On Jun/29/2023 17:35 (Moscow time) Educational Codeforces Round 151 (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, 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:

**WORK & STUDY OPPORTUNITY IN BARCELONA — IDS x HARBOUR.SPACE UNIVERSITY**

*Intentionally Designed Solutions (IDS) has partnered with Harbour.Space University to offer Master’s degree scholarships to study Front-end Development, as well as work experience as a Front-end Engineer in a leading product development studio specializing in web-based solutions, including websites and web applications.*

*All successful applicants will be eligible for a 100% Tuition Fee Scholarship (29.900 €/year) provided by the Intentionally Designed Solutions (IDS).*

**CANDIDATE’S COMMITMENT**

**Study Commitment:** 3 hours/day

*You will complete 15 modules (each three weeks long) in one year. The 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.*

**RESPONSIBILITIES**

*Collaborate with cross-functional teams to develop and implement innovative front-end solutions that align with project requirements and design specifications.**Write clean, efficient, and maintainable code using modern front-end technologies, including Typescript and Svelte.**Ensure seamless integration of front-end components with back-end systems, leveraging technologies such as MongoDB and Firebase.**Demonstrate a basic understanding of smart contract technology, enabling the integration of wallets and blockchain functionality into web-based products.**Lead and mentor junior developers, conducting code reviews and providing guidance to improve code quality and development practices.**Drive the development arm of IDS's business by identifying opportunities to optimize processes, enhance efficiency, and improve overall team productivity.*

**REQUIREMENTS:**

*Minimum of 2 years of professional experience in front-end development, with a focus on web-based products.**Strong proficiency in Typescript and Svelte, with a solid understanding of front-end frameworks and libraries.**Experience with back-end integration, particularly with MongoDB and Firebase.**Basic understanding of smart contract technology and its application in web development.**Previous experience managing and mentoring developers, conducting code reviews, and improving development processes.**Excellent problem-solving, communication, and collaboration skills.**Bachelor’s degree or equivalent experience.**Advanced English level.*

**UPD:** Editorial is out

As a

greenparticipant, I hope to becyanagain afterthiscontest)If you want to raceJust replyGL & HFAs a cyan

participant, I hope to begreenagain after this contest)GL & HFAs a blue participiant, I hope to be a LGM ever. GL & HF

As a blue

participant, I hope not to beblueagain after this contest)GL & HF

What's in blue when you can become cyan with no efforts.

what's GL&HF?

good luck and hi fi

But i knew

Have FunxDAs a

grayparticipant, I hope to staygrayafter this contest)GL & HFMy answer also same :)

You Stole my name !!!

As a black and un-bolded

participant, I hope to beblack and un-boldedafter this contest)GL & HFI hope to be purple.

As a

Purpleparticipant, I hope to stayPurpleafter the contest.As a gray

participant, I hope to begreenafter this contest)GL & HFI might become cyan by morning if not hacked.

As a gray participiant, I hope to be a LGM ever. GL & HFThat's so good.

as codeforces user i hope to have great round

Again no tester

big chance to become green tomorrow

i guess you wont become green and I wont remain green

sad :(

.

The road to green, God willing

bro wdym, you don't even need God to make it to green. I have full faith in you! :D

We can't do anything without the will of God

Yes, my bad. Let's pray that god will be generous and allow us to advance to the next color.

its god's will that i am dog shit at data structures&algorithms

bro I'm awful at dp

dud u burn in hell like this what are u even saying?

almost there mashaAllaah

Good luck, God willing

Will "not rated participant" get rated in this contest?

Non rated participants always get rated if they participate. Which is why you should participate. GL! :D (Remember to bump)

I want everyone to take it to the next level

Why can't the code submitted now be viewed on the PC side?

who tested this round?? who tested this round?? who tested this round?? who tested this round??

I thinkNOBODY!!NOBODY!!NOBODY!!NOBODY!!Does it better, iykyk XD

Nice contest, but there's just one small problem with it: who tested? like genuinely who tested? who gave you the testing code? I'll tell you nobody did, nobody tested it. There are zero people who tested among us, look I invited everyone who tested to this party, and took a photo of everyone who tested, yo check out it's a bus full of everyone who tested. You know what man, I'll do you a favor, clearly we can't see who tested, so I'm just gonna do it myself, I'm gonna find out who tested. I sailed in the seven seas to find out who tested, yo I literally found the one piece before I found who tested, I literally climbed to the top of Mount Everest and didn't find who tested. Keep searching boys we gotta find who tested. I just infiltrated the largest satellite dish in the world and I still can't locate who tested, I literally found the cure to cancer before I found who tested, I'm on maximum render distance and I still can't find who tested, I witnessed the collapse of human society resulting from a global nuclear war, I now live in the grave of this broken world ravaged by radiation for years on end before I found who tested, I visited every single planet in no man's sky and still didn't find who tested, doctor strange literally looked through 14 million different timelines and not in one of them than anyone tested, I literally searched through every single backroom's level and didn't find who tested, I literally died and went to heaven and god himself doesn't even know who tested. Leaving the earth's atmosphere to expand the range of our search, yo I literally found extraterrestrial life on Mars before I found who tested, I have achieved intergalactic travel before I found who tested, I just found a dyson sphere before I found who tested, I found the edge of the universe before I found who tested, I literally visited every single planet in the entire universe before I found who tested, I am literally witnessing the death of almost every star around me before I found who tested, the light of the universe is slowly fading I have searched across galaxies leaving no stone unturned, yet I am afraid my time in this universe is finally running out, it's a shame really I've witnessed stars being birthed and those same stars dying, I've seen literally everything there is to see in this beautiful universe, yet this whole time I've been caught up with such a petty task instead of enjoying my time while it lasted. I was distracted from the beauty of it all I don't regret what I've done, though the question that started it all: who tested has finally been answered. I've searched every nook and cranny in this entire universe and can now confidently say better than anybody that truly nobody tested [Music] the contest.

As a cyan participant I hope to go green this round.

Happiness both ways

I hope to go cyan this round, but I think it's impossible

Yes. +106 is very difficult to get at once. you are closer now.

What's the difference between common round and Educational round?

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

keeping it simple --> difficulty level is

DIV.2and Penalty is likeDIV.3:/As a blue participant, i hope to cross my peak rating :)

GL & HF

Maybe I am ready to take the next step.

Is that Bokita?

Problem C was really something..

how to do C with binary search?

observation !!

Read 2nd testdata of testCase 1 in the example. You might get it.

Can you elaborate please.

s = 123412341234

m = 3 ,

l = 111 r = 444

So, Now, Traverse the string S from left to right. While doing so we need to keep track of zero'th digit of the password, until all the characters are occurred from l[0] to r[0]. Once all the character of particular digit of password are occurred in the string, we must move to next digit of the password.

1234| (now all the characters are occurred from first digit of password, so we must move to next digit).

If all the digits are exhausted from password, then answer is not possible. otherwise, answer is possible.

got it,thanks.

wouldn't it will give

TLEfor checking through all Possibilities of password. and thanks for hint of BS.Yeah,that is what I thought suppose m =10 and l = 0000000000 and r = 9999999999 then we have to check at least 10^10 passwords. Don't we??

Man, I solved it with DP, shame on me

I get this approach but where does binary search come into play here? The traversing is linear

where Did I mention anything about binary search ?

Vincenzo_ was asking for BS solution and you replied to him so I thought you may be telling something about the BS solution. Anyways do you have any insight on how to do this via BS? I am seeing a lot of people discussing BS solution of problem C but I dont find the approach mentioned anywhere.

Can someone give a hint on E please?

You can squeeze in $$$O(NK^2)$$$

I was thinking about something like doing a dp which keeps track of three parameters: current idx (n), current one, and wasted moves

would this work ?

This would, trivially implementing this is $$$O(NK^2)$$$. To squeeze it in, you can do the following: 1. If more than half of the array are $$$1$$$-s, you can consider that every box without a ball has one, and vice versa. This halves the runtime. 2. Write out the formula: $$$dp[i][k][p1] = dp[i - 1][abs(k - pos[p1 - 1])][p1 - 1]$$$, where $$$i$$$ is the current position, $$$k$$$ is the number of wasted moves, and $$$p1$$$ is the number of wasted moves so far. Notice that you can keep this dp in a single array and recalc top to bottom, so you do not do memsets and swaps.

As someone has written, it might work not in $$$O(NK^2)$$$ but in $$$O(NK\sqrt{K}$$$)

How far did you get/what part of the problem do you want a hint for?

I think there are several stages in solving this problem:

(I failed at step 4.)

How many people solved Problem C, ** AFTER READING SECOND TESTCASE DATA in TESTCASE 1 ?**

:| I didn't read the explanation of test cases question was quite self explanatory!

Oh I am glad, I am not alone.

How to prove that if answer is no then the string must contain such a pattern?

How??

can you please tell what helped you in

AFTER READING SECOND TESTCASE DATA in TESTCASE 1 ?, i didn't get it , is this testcase so obvious for BS. how did it helped solving the quethere is no need of binary search, it can be done by linear search.my approach is:- try to find max first occurance position of elements of l[0] to r[0] and store it in last_position and then find from last_position+1 position for l[1] to r[1] and update the last_postion. if it goes beyond (size of string-1) ever then possible otherwise no. basically each time we are discarding max possible substring from left side ex:- 123412341234, 111, 444 for l[0] to r[0], last_position=3, then start searching from 4 for l[1] to r[1], last position will be 7 and for l[2] to r[2], last position would be 11 (string size-1=11) so ans is no. this example was a good hint for this approach but i didn't get it that time.

thanks bud, I also had same intuition while reading the test case, but was not able to apply it through code while contest.

It can be solved by dp also . use two state dp , dp[i][j]where : 1) i denotes the index in string s. 2) j denotes the index in string that we want to make( that is of length m). this j will help us in iterating through l and r string.

How to do D?

My intuition was maximizing this, pref_sum [i] + max(suff_sum[i + 1], ..., suff_sum[n — 1])

You need to do

`max(suff_sum[i + 1], ..., suff_sum[n — 1], 0)`

instead.I think pref_sum[i] should also be included?

For this test case

2 -1 3

Why answer can't be -1?

If your answer is -1, then the player's rating will go 2 to 1 to 4.

The answer should be 2. The player's rating will go 2 to 2 to 5.

Any answer other than 2 will result in the player's rating decreasing from the -1. If our answer is 2 then we ignore the -1.

It seems to be correct as that's I what I've done. I find the continuous interval with the smallest negative sum, and then remove it.

I'll try to explain my solution in my own words. First, define C[n] as the prefix sum of A[1..n] (formally: C[0] = 0, C[i] = C[i-1] + A[i] for 1 ≤ i ≤ N). The elements of C are the scores that would be obtained if there wasn't a floor in effect.

Hint 1Then it's optimal to choose K as one of the elements of C.

(Sketch of proof: if we choose K between two values of C, we can raise it up to the next value of C without making anything worse.)

Hint 2If we pick K = C[i], then the total score obtained is C[N] + (C[i] — min C[i..N]).

(Sketch of proof: if we put the floor at C[i], then the last time we will hit the floor is when C[j] (j ≥ i) is minimal, because if it were possible to hit the floor again at, say, index k > j, that means C[k] < C[j] and thus j wasn't minimal. When C[j] < C[i], the floor will change the drop in points from C[i] — C[j] to 0, which is why we add C[i] — C[j] to C[N]).

ImplementationCalculate C from A. Then walk through the array from back to front, and keep track of the minimum value of C[i], C[i+1], .. C[N]. Both steps are O(N) obviously.

(During the contest, my dumb ass used a priority queue instead of just tracking the minimum.)

Code: 211553817

Thank you for this, was searching for a detailed explanation from last 3 hours

thanks it was very helpful. I made a graph of an example of C[i] and k, it helped me understand.Your text to link here...

Thank you, this is very helpful

explain solution for C?

I bootled this so bad . I got accepted after 7 minutes of contest end , the idea is so easy i just messed up the implementation :

idea is that after you choose a number the first occurrence of that number splits the string into two, now the problem reduces to the right half only . so we can greedily choose the number from possibilites (that is between l[i] and r[i]) which gives the shortest possible remaining string. If at any iteration (i) one of possible numbers is not in the remaining string choose it and that gives answer yes. If you finish traversing all i's without then the answer is no.

code :

https://codeforces.com/contest/1845/submission/211531378

SpoilerI proposed a DP solution. Let dp[i] denote the maximum index of elements

`l_i`

to`r_i`

in`s`

due to which a subsequence =`pass[1...i]`

is produced. At any point, if the index becomes infinite (i.e. element not found in the database), then we have found a password.Transitions: For

`l_i`

<=`j`

<=`r_i`

`dp[i] = max(dp[i], right[dp[i-1]+1][j]`

where

`right[k][j]`

gives the closest index of`j`

to the right of`k`

th position in`s`

.`right`

array can be precalculated.Ans. is

`dp[n-1]>=n`

Start from last in both range strings(l and r) and string s, let say p1 = n-1, and p2 = m-1.

Now, looking from last (i.e from p1 to 0), find the numbers in range l[p2] and r[p2], if at any p1, you find all the numbers in the range, then reduce p2, then again find all the numbers in range l[p2] and r[p2], do this until you will encounter one of the case, if p1 becomes -1, then that means you can make some password which will not be subsequence in string "s" therefore the Answer would be "YES", else p2 would have became -1, that means all the ranges have ended therefore all the possible subsequences are present in string "s", Hence the Answer would be "NO".

Spoilerhttps://codeforces.com/contest/1845/submission/211482609

Yet again I misread a problem, this time C. I thought it was asking to check if there exist a string s, such that s >= l && s <= r, instead of s_i >= l_i && s_i <= r_i. (mathjax not working?)

Overkilled D with binary search and sparse table and now feel very annoyed at myself. :(

How did you solve D with binary search and sparse table? I am curious to know. My technique used a modified version of kadane's algorithm to solve it.

Fix the position of k then find the smallest subarray starting at that position that has negative sum. Rating will be k after that. Repeat until there is no more subarray with negative sum. Rating at the end will be k + suffix sum from there. To simulate the above process run a binary search for the first index where sum of subarray starting at k's index is negative. Sparse table helps here. Yes it's overkill. And it's basically the same idea

Oh I got your idea. True it is a little overkill but still its cool. Also it feels like my idea but from the opposite direction. My idea was to find the max sum subarray that ends in the last index of the array containing all match values. I would then add it to k.

D is a neatly disguised minimum subarray sum problem

How to do E? I have a O(n^2 k) DP which TLEs. Is this the intended solution, or is there anything faster?

is it

`dp[i][j][p] = how many possible placements are there if the ith ball is at jth position and we have used p swaps so far`

in the end answer is =

( I just asked this to confirm if my idea was correct )

I used the fact that if $$$one_i$$$ is the position of i-th one, possible final positions for i-th one are roughly $$$[one_{i-\sqrt k}, one_{i+\sqrt k}]$$$. If you use this then there is only $$$O(n\cdot k^{1.5})$$$ states.

How this fact can be proved or even how can it be observed?

Ones don't change their relative order, so to move $$$one_i$$$ to a position $$$x < one_{i-\sqrt k}$$$ you need to also move all of the other occurrences to the left. In the simple case when all of $$$one_{i-\sqrt k}, \dots, one_i$$$ stand one after the other you will need to make at least $$$(\sqrt k + 1)^2$$$ operations, and if they are not consecutive it requires even more operations. Not very strict, but I hope this helps.

thanks!

That's great observation, thanks

Congratulations for coming up with the $$$O(n^2k)$$$ DP! My solution is simply an optimization of the $$$O(n^2k)$$$ DP and the time complexity is $$$O(nk\sqrt k)$$$.

In one word: throw away all useless states.

In more words:

DP is deciding from the left to the right for each position whether to put a

`0`

or`1`

and count the number of inverse pairs (aka number of swaps used). Let`DP[i][j][p]`

be the number of situations that: we have already decided the first $$$i$$$ positions, among them we have used $$$j$$$`1`

s and we have encountered $$$p$$$ swaps. Naive implementation of this DP is $$$O(n^2k)$$$, but a state is useful only if $$$\left|j-S_i\right| <= O(\sqrt k)$$$ (where $$$S_i$$$ is the prefix sum of the original array), otherwise the number of swaps will be too large ($$$>k$$$).Source: Trust me. I am gray.

Hi, could you point to a resource where one could practice such dp problems? I've done a few on cses.fi, and SPOJ but Even the O(n^2k) DP is a bit difficult for me to grasp and I'd like to learn more. Thanks :)

edu contest with 999999 caseworks

Can any one explain to me why my B submission is not working?

Your first case of

`if`

is incorrect.It should be 1+min(abs(xb),abs(xc))+min(abs(yb),abs(yc)).

Did 3D DP for C worked for anyone?

2D DP with $$$O(100m log(n) + n)$$$ https://codeforces.com/contest/1845/submission/211518255

Can you please explain your algorithm?

Managed to make a really messy DP solution in $$$O(nm)$$$

https://codeforces.com/contest/1845/submission/211527425

Greedy & Binary Search)

actually you used binary search

O(nm) worked for me

The gap between question D and question E is too big, but of course, it could be mainly because I am too weak. Let's do better next time, although I am still a little disappointed.

I overkilled

`C`

with`DP`

and I don't feel good now SubmissionIt's impressive to be able to solve this problem using dynamic programming. At first, I also thought it could be solved using dynamic programming, but I couldn't figure out how to do it no matter what.

Main idea is to store dp[i][j] — maximum value of "where we are" in the string s if the i-th digit of the password is equal to j. Transitions are handled by searching for the next occurrence of the next digit and updating the dp value accordingly.

And this problem should deliberately retain the time complexity that can be achieved by using dynamic programming, because if a greedy approach is used, m can be larger.

Yea me too. First I misread the problem, then I overcomplicated it with dp, After that fortunately I just had enough time for D

Can you describe your DP approach? I'm trying to learn DP these days.

Can't think of any approach for

C? Someone please provide some sort of hint like in which direction should I think?There is a strong independence between each digit of the final number. You can consider the optimal scenario for each digit and try to solve this problem using a greedy approach.

If you know the problem colorland in Kattis, this problem is similar to that, you build an implicit graph from the start of the string to an "INF" node and see if there is a path of length <=m from left to right. (Note: you can greedily jump as far as possible!) You could maybe see my solution for more clarification.

could you please provide the link of the question which you are talking about?

(colorland in Kattis)Sure, https://open.kattis.com/problems/colorland

Also, I just managed to find time today so I wrote a small explanation here: https://codeforces.com/blog/entry/117727?#comment-1042026

Hope it might help you understand it better, feel free to ask if you need more clarifications.

thank you for helping me out

Our goal is to create a password that contains any subsegment that does not exist in the given string as a subsequence in other words, We don't need to generate all possible subsequences of the given string, but We need to check for a combination that will not exist as subsequences this way we can use dp to optimize our brute force solution to find a sub-combination that will make a valid password.

can anyone share their greedy/binary search approach for C?

Sure, to solve it using greedy approach, one might try to think of how to build a string that would not be a subsequence.

To do so let's think of positions of possible values of first digit of resulting password. It definitely should be from l[i] to r[i]. For all such digits let's find their first positions in the string. I claim that it is always beneficial to take digit with maximum value of first appearance. Why? Well, because it destroys more possible subsequences (since we cut off the largest prefix by doing so). See my submission for more details: 211498000

Nice approach, very easy to understand, tysm

Very nice solution! Thanks

I understood your approach but could you please tell me what this line does?

SpoilerOf course, for pos[d] I store indexes where digit d appears in s (in reverse order). Now, when I try to greedily build this “bad” subsequence I interpret first appearance of digits as a candidate that can now become new digit of resulting password. When I have chosen this new digit, I know its position in s (it is p), so for all digits from 0 to 9 I want to stop considering ones which happen to have positions <= p.

Storing in reverse order is very beneficial because it let’s me to delete element from a vector in O(1) and resulting complexity of solution is O(n + 10 * m)

Hope this helps

Take an index starting from the beginning of the given database string. Now consider first range of allowed characters for first digit — [l_i — r_i], move the index forward until all characters in this range have appeared at least once (I used unordered_set for this). Similarly, do this for all password positions, index always moves forward. If index reaches end of string while there are still digits in password left to be considered, answer will be yes, otherwise no.

Did someone try it using binary search? I did it but Gave TLE for me :(

Haha, I sucked, couldn't solve D.

can anyone explain the approach of problem C ?

Here's my approach, Take an index starting from the beginning of the given database string. Now consider first range of allowed characters for first digit — [l_i — r_i], move the index forward until all characters in this range have appeared at least once (I used unordered_set for this). Similarly, do this for all password positions, index always moves forward. If index reaches end of string while there are still digits in password left to be considered, answer will be yes, otherwise no. 211508945

Can anyone share their approach for D?

just find the largest decreasing subarray of input and avoid it, then we get the maximum rating

Let's denote prefix sum to position $$$i$$$, by $$$pref[i]$$$. If you think about it a little, it's easy to see that answer must be in $$$pref$$$ (unless there is no positive value in $$$pref$$$). Let's say that our initial answer is 0, and iterate over $$$pref$$$. Assume that before position $$$i$$$ we found some answer $$$x$$$. Now, we have to find some conditions to determine if it will be optimal to change our answer $$$x$$$ to $$$pref[i]$$$. Surely, it won't be optimal, if $$$x > pref[i]$$$. Otherwise, let's denote the prefix sum to position $$$i$$$, if $$$x$$$ was the threshold by $$$pref\_ans$$$. If there is some value $$$min\_val$$$ in $$$pref[i]$$$ on positions $$$[i+1, n)$$$, such that $$$min\_val + (pref\_ans - pref[i]) < pref[i]$$$, then it will surely be optimal to change our answer to $$$pref[i]$$$ (because if $$$x$$$ was our answer, prefix sum here will fall below $$$pref[i]$$$). Otherwise it won't.

Does someone knows if in problem E, DP with cost $$$O$$$($$$n^2$$$$$$k$$$) is hackable, I got TLE :/ 211505619, but I have seen some AC 211506794 or 211522102

Anyone did D by binary search???

i want to know the same.

You've to be sure about monotonicity of your search space whenever you're going for binary search, which in this case is not monotonic.

Was c really that easy or I guess i am too dumb as 4k people solved it

C was easy. but the statement(possibly poor) made it a bit complex.

sorry but problem C statement was poor. you should have highlighted "i-th digit of the password has to be between li and ri, inclusive" with a bullet point :'3

Problem B, why is the answer to this 1 and not 2 ? 1

1 100000000

1 99999999

1 2

answer is 2.

Any good hint for E, please? Want to solve it myself

That's truely educational round and i learned i should quit cp

Anyone else who felt that D was easier than C?

C is the easiest task after A

B was easier than A.

.

Can someone explain what is wrong with this solution?

It is failing for following in online judge but is working in my local machine: 1 2 1 99999999 1 1

You're adding an additional 1 after 2nd if case.

Any hints for E?

Problem E when I do rolling table using two 2d arrays

:oh no!!!,you are too slow!!!,get TLEProblem E when I do the same rolling table using one 2d array by clever variable saving and iteration

:Congratulations!!!,you are accepted!!!It's kinda strange but in E the small trick with changing all zeros with ones and ones with zeros, if the number of ones if more than half, works and makes O(n^2*k) solution pass. I think it's strange and if it's not the intended solution, time limit should be smaller. 211535929

there exists n * k^1.5 solution but it takes a lot of time....

What do you guys think is the rating of problem C and D?

C ~ 1400

D 1600-1700

can anyone share approach for D?

Can anyone find a testcase where my code for B fails?

Why is this solution showing MLE in pypy3? I was shocked by this. It's AC in C++ Link: https://codeforces.com/contest/1845/submission/211534174

lol

I'm so dumb that after reading the statement of C, I thought it is digit dp and waste for an hour to write. Then I realized it does not require to make the password from l to r(like 40 to 50 I thought they were 41,42,43...), it is just in range, digit by digit. I solved by the way, but it still got me negative delta. Hopefully for better luck next time :((

as a green, Hope to come close to cyan.

Problem C ... Can anyone tell me how the answer here is "yes"

s = "01342104424232424004113131423112311240" ,,,,

m = 5 , l = 23004 , r = 24244

Could you write the case more clearly?

I think it became clear

23104

Thanks I think I misunderstood the problem.

because you can choose 2 3 1 0 4 :

01342 -break- [104424232424004113131423112311240]

10442423 -break- [2424004113131423112311240]

24240041 -break-[13131423112311240]

13131423112311240 -break- []

[] no more elements to choose [4,4] from hence answer is yes

I hate how non intuitive problem D is. I am still not able to convince myself how the prefix sum just behind the minimum subarray is the answer.

Edit: Got it now. If we choose k = prefix[i] and if there exists a j(>i), such that prefix[j] is the smallest among prefix[i+1...n], then the elements from i+1 to j would contribute effectively nothing to the ratings.

exactly, can someone share how they reached this conclusion and their thought process during solving the problem?

After you fix the prefix sum till index $$$i$$$ as the current $$$k$$$, you can keep adding elements to your current sum until it dips below $$$k$$$.

This will be when the sum starting from index $$$i + 1$$$ just becomes negative, which is when the prefix sum becomes less than $$$pre[i]$$$.

Since we can't go below $$$k$$$, we just stop at $$$k$$$. This means we just ignore this subarray and do this process repeatedly: find the next index where the prefix sum is less than the same at our previous position, ignore it (since the subarray sum will be less than zero) and set that as the new position.

If no index has prefix sum less than that of our current position, our subarray can be extended till the end of the array since the sum will be positive. This will occur only at the minimum of the prefix sum array (let us call this index $$$mn$$$).

So, the answer when $$$k = pre[i]$$$ will be $$$pre[i] + pre[n - 1] - pre[mn]$$$ (or just $$$pre[i]$$$ if $$$i \geq mn$$$).

So, the maximum value of this expression will obviously be $$$\max_{i \leq mn} (pre[i]) + \max(0, pre[n - 1] - \min_i (pre[i]))$$$.

I solved this question and I still don't understand the intuition behind it.

Here are some less complex observations for problem D :

Let's make a prefix array first. Now, our answer is definitely from one of the values in the prefix array.(or 0 if all prefix values are -ve). Why? cuzz we won't let our rating fall from a point where we reached , so out k must be a value we reached.

We can calculate answer for each prefix value (though it's easy to prove that optimal value is always a local maximum).

Begin traversing the prefix array now how to calculate the answer from this value of k = prefix[i] ? ---> Answer is : [ Σa_i + (maximum distance you go

belowfrom k in you prefix array) ]How to prove this ? ----> You can think of it as : When you add something -ve that takes your prefix value below the threshold k, you actually add some

EXTRAto your answer to keep it fixed at value k. Hence , whenever next time when again prefix value goes below k , again add value toEXTRAto keep it at k. Finally you will notice you added totalEXTRA= max(0 , k — min(pref[i])).--> min(pref[i]) is minimum prefix value that we reached.

Thanks for the explanation, I tried to do something similar by fixing the answer as any one of pref[i] values. Then I calculated the max rating possible when k = pref[i] by adding all +ve values after arr[i] to k, since the rating won't go below k. However where this goes wrong as you might have guessed is that if I fixed k as threshold from the start the rating would not be k when I reach arr[i]. Is that where the

(maximum distance you go below from k in you prefix array)in your solution comes into play? I still do not understand what Σa_i is tho, could you please clear that?That's just sum of all ratings

What could be a possible rating for D ques I thought on the same line but was not able to find the resultant score by fixing k in constant time.

I did this for every i, k = prefix[i]; resulting score = prefix[n] + max(0, prefix[i] — min(prefix[i + 1]....prefix[n]))

I had a weird idea for C, for a password to not be a subsequence there must exist two indices in it for which it's not possible to get a subsequence from the database, we can brute force for the indices and the possible numbers on them, if these values are indeed the pair of two indices, then either all the occurrence of one is left to the other or this indices maybe belong to the the first m and last m of the database, pretty weird I know :p, someone thought something similar? This is idea, I don't know if it works

WHAT I DID STARTED WITH INDEX POINTER 0 NOW I TRAVERSE THE L AND R STRING FROM STARTING FOR EVERY DIGIT (0 , 9) IN [ L[I] , R[I] ] FOUND THE MAXIMUM INDEX IN MAIN STRING THEN SHIFTED THE INDEX POINTER TO MAXIMUM

IF NO CHAR IS PRESENT IN MAIN STRING — > HENCE NO SUBSEQUENCE CAN BE GENERATED -> "YES"

PS : TC 2 HELPED A LOT :)

My idea for E. No idea if it's correct or not:

why cant D be solved using Ternary search ?

I believe it’s because your function might evaluate to the same value for intervals of input, and if that’s the case your ternary search will not be able to decide which side to move to.

Because $$$f(x)=f(x+1)$$$ might hold for some cases where $$$x$$$ represents $$$k$$$ and $$$f(x)$$$ represents the value got with $$$k=x$$$.

Please anybody give me hint in D problem. I don't know why am I getting wrong answer. Submission --> 211537213

I've tried, scroll above

First time I saw your solution, I didn't get it. After drawing graph of prefix array everything was crystal clear. That's not very hard problem. Lol:)

Any traders realized that D was just maximum drawdown in your average backtest haha?

lol. I thought about my cf rating chart while solving D

what is the test that hacks problem a?

it's against the rules

Please implement same rating system as problem D here too. I don't want to go below expert.

what should be correct output for this test case in problem C

if correct answer is "NO" then please explain me why

Oh now i got it

it's

between li and ri inclusivei.e. it's range rather than ri or li spent whole contest on C :<(it is invalid input, every l[i] <= r[i]

if you mean l = '3', r = '7', then answer is "YES", u can choose '7'

As a gray shekhar_46 user I wanna Green after this contest

Worst E question I have ever seen!..

If it has a solution better than $$$O(N*K^2)$$$ that I cannot be able to find then it is okay but if the original solution is to make optimizations on $$$O(N*K^2)$$$ then it is really bad!

there exists n * k ^ 1.5 solution which is pretty nice and educative....sadly authors didnt expect cubic passing (i blame edu rushed preparation)

Can someone give a hint to solve D using Binary Search?

max(pref_mx — mn( mn after pref_mx ))

answer mx_pref

author of D pranker ):

Here's an O(N^2K) solution to E that passes in 655 ms. submission

There are no optimizations other than the fact that if more than half the array is ones, you can swap them with 0s. This reduces the solution by a factor of 2.

The original solution (without the optimization) passes in around 3000 ms

I don't think an E-question that blocks time is meaningful.

Is it possible to solve D using ternary search ?

Nope, for the input:

we get:

for k = 0: 5 rating

for k = 1: 3 rating

for k = 4: 4 rating

.

https://codeforces.com/contest/1845/submission/211653651 can you tell me where my code is failing

Lol! I solved A using the logic of UnboundedKnapsack rec code....

When will there be a tutorial? Or do you already have it but I didn't see it? 什么时候会有教程？或者说已经有了只是我没有看见？

Very ImportantI am a Newbie — @787. Yesterday I solved one question in the round successfully but my rating remained as it is. Why my rating did not increase even on solving one questioncause the contest is open hacking, after that all submition will rejudge and your rating will increase

thanks

Result of the round is not declared yet.

thanks

why in custom invocation my solution (of problem A) is working correctly, but when I submit, it says "Wrong answer on test 1" (that is example)?

does anyone know why my ranking did not change even after solving the C problem?211519289

Easy Solution for C: 211519289

Hacks:A:WA: 665; RT: 1; TL: 1; ML: 1.B:TL: 2.C:TL: 85; WA: 2; ML: 1.[An uphack to C (TL) has been counted.]D:TL: 14; WA: 3.[An uphack to D (WA) has been counted. ]E:TL: 2.F:(None.)Total:WA: 670; TL: 104; ML: 2; RT: 1.Count:777Could anybody explain why there are so many hacks?

bc of no testing and weak tests.

I didn't imagine so many people would stumble at A

Why was problem D so easy?

So many Cs and Ds were hacked via TLE. Please explain how to get a code to give TLE. I tried larger inputs, but the system constraint is that input can't be bigger than 256kb. So I could only make use of some of the input constraints.

It can be done using generator, got it now. Sorry for naive question, I'm new to hacking.

I guess the idea of problem c was taken from https://cses.fi/problemset/task/1087

This was a fun round. Cant wait to become rated.

My submission was having an indexing issue in all cases. Still it passed during contest. But it gave RE on test 3 in system tests. Fixing the indexing issue gave AC.

Why it did not RE during contest?

Participant hacking test cases will be added after the hacking phase, maybe you failed one of them.

That means if one participant being hacked, all similar solutions will be failed in the system testing phase.

Since it failed on third test, it means they kept only 2 tests. They should have kept more tests

There were at least 3 tests for B during the contest (the submissions show some people getting wrong answer on test 3) so if it was an indexing issue (e.g. leaving the bounds of the array) then the FST was probably because of undefined behaviour. During the contest it didn't cause issues, but you got unlucky with the system tests and accessed a part of memory that you couldn't access.

exactly 3 in fact...but still too few.

What are you talking about? You haven't even participated to this contest.

I did with alt id

Just look my D solution: https://codeforces.com/contest/1845/submission/211528371

For Problem D, I have tried binary search on answer. I'm getting WA on test2. please can someone help me rectify my code. 211583193

I don't think the answer k satisfies some requirement to apply binary search. Assume the right answer is k, then 0 and inf will get lower rating than k. It is at least a single peak function that cannot apply binary search. By the why, I guess it cannot be solved by observing the rating's pattern of different ks. I solved it by trying all possible ks that can be the answer. There are only O(n) candidate ks and it is small enough to pass the problem D.

i got either 0 or anyone of prefix sum value will be the answer.. but how to find which one will yield the maximum rating. I tried binary search on pref sum values now.... but it is giving WA on test 2 ... case 51.... suggestion plss 211608959

I seldom solve the C in div2, but I solved it this contest and I think I will be pupil again. However, my A is wrong in fst. oh my god.

When got my rating up?

There was no rating changes for me after this contest even though i'm in div 2. Thing is, this is the first contest i've performed well in a while so i'm maybe being a bit paranoid but was this round declared unrated? i really hope that the rating changes were just delayed for a little bit

update rating when??

Rating was updated

Problem Ccan anyone please explain the approach to get position of ith element in string using 2D vector nxt, is there a name for this approach , coz i have seen such code many times. submission:https://codeforces.com/contest/1845/submission/211443935Your link isn't accessible by the way.

How I visualized it is like this: consider first the $$$m=1$$$ case. Obviously what we do is check every digit $$$d_1$$$ between $$$l_1$$$ and $$$r_1$$$. If $$$d_1$$$ does not appear at all in the string $$$s$$$, then we output "YES" because $$$d_1$$$ will definitely work. Otherwise if no such $$$d_1$$$ exists then there is no viable value for $$$d_1$$$, whence we cout "NO".

Now let's try the $$$m=2$$$ case. For the first digit $$$d_1$$$ we do the exact same as above, but this time even if every possible $$$d_1$$$ between $$$l_1$$$ and $$$r_1$$$ appear, we might still be able to generate a valid passcode if $$$d_2$$$ doesn't appear in the string $$$s$$$ after $$$d_1$$$ does. To maximize the possibly of this happening, we will try to pick the first occurrence of $$$d_1$$$ to be as far right as possible, so that there is less digits of $$$s$$$ that can block $$$d_2$$$ from succeeding.

But how do we do this? The $$$\mathbf{nxt}$$$ array is what comes into play here. Let $$$\mathbf{nxt}$$$ be a $$$10$$$ by $$$|s|+1$$$ array such that $$$\mathbf{nxt}[i][j]$$$ is the (1-based) position of the next occurrence of the digit $$$i$$$ after position $$$j$$$ in $$$s$$$, or INF if no such position exists. (Long sentence, sorry.) Then the algorithm will be something like this:

This now obviously generalizes to any positive $$$m$$$, I trust you can carry on the analysis from here :)

edit: minor typos, sorry

Good explanation. Bookmarked your answer

As ratings have been updated and hack phase has ended, when editorial?

Can anyone explain me dp approach of problem c

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).[DELETED]

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

Can someone please give complete , easy to understand explanation of Problem E explaining it in easier steps , it would be very beneficial as it seems very very difficult to even understand anything about the problem rather the problem statement and editorial is way too tough to understand , it would be very helpful

Hi im a newbie on cf, any tips to reach specialist? i get stuck in adhoc/greedy problems.

what do i do now??? please help

Attention!

Your solution 211471860 for the problem 1845B significantly coincides with solutions Isaac_Netero/211471860, musthang/211512249, lepsinach/211512269, atulya_codes_/211516053, hatikyu/211516437. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Attention!

Your solution 211505041 for the problem 1845B significantly coincides with solutions cpnhihori/211494126, Sk_4036/211505041,

ShaRingan/211517241, techie_2304/211521482. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.It's just a coincidence... I used a simple way of calculating the standard distance walked by Bob and Carol. In the first of the code, I included a standard library, then used a while loop for the testcases, then six inputs where they are now present, and then where Bob and Carol want to go—then initiated an integer with value 1 because they are initially in the same cell according to the question. Then used, the if statement for the conditions on their X-coordinate cells if they both wants go down or up with respect to cell A. Then calculate the absolute minimum difference between Bob and Carol with respect to Alice and add this difference to the value initiated with 1. Same condition Y-coordinate cell and same procedure. Then finally, print out the number of common cells traveled by both of them.

So I didn't copy it from any of the online sources. The code logic both are simple, so I request you to please consider my solution.

.

This is the first time I have received such a warning, and it is evidently a false positive. I have never used any online IDE or commonly published source for competition purposes. I believe this is merely a coincidence, as the solution to problem D is fairly straightforward. Although my rating was not affected since I participated outside of the contest, I would like to appeal against this conviction. Thanks!

Attention!

Your solution 211480048 for the problem 1845D significantly coincides with solutions coderbd/211480048, randomIsNotRandom/211495795. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

why ratings are rolled back of this contest? will they be rolled over again?

why is it unrate now?

[DELETED]