Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.

On Jun/27/2024 17:35 (Moscow time) Educational Codeforces Round 167 (Rated for Div. 2) will start.

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, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

**UPD:** Editorial is out

Good!

Hello hope to reach CM in this round so write me a tip that you think it's useful on rounds :)

pray.

one tip: Please hope realistic

I think you forgot that you are 1634 instead of 1834...

prolly you should pray not falling back to cyan...

Solve A-F

I hope to be able to solve 3 problems during the competition

So do I

Still confused how 1800-2400 rated guys make 3000-3500 problems but mk

Look out for the author's history rating. You can come up with a hard problem despite your rating.

Does this contest have open hack ?

yes 12 hours open hacking phase

I did not steal the code or cheat, why did you skip it?Now it seems like I will become pupil in 3024

quite a similar graph with me but keep practicing

I already gone into 3rd year.....but still on newbie

After my 3rd year, I became a Specialist from a Newbie. No need to worry.Push yourself hard.

Some tips how you went from range of more than 8k ranks to 1k rank in last round in just 2-3 months?? Did you followed some course or what??

Tbh, I didn't follow any guides for the summer grind. But, what I feel make me enhanced is:

Daily solving of POTDs on GFG, Leetcode.

Participated in almost 20-30 contests in the span of 1.5 months on several platforms such as CodeForces, CodeChef, Leetcode, etc.

Very IMP,

UPSOLVE.Learning very new concepts related to the problems I have encountered.

The only suggestion I can give... "Be Consistent, Just DO IT."

Edit: Try to keep up your motivation all the time. For me, It's watching the performance of my friends, fellow CPs, and legends. Don't compare to them.

Comparing is the thief of Joy.- some random reelwhat about me

good luck and +delta for everyone

Thanks for all ur contribution!

Hope to achieve positive delta in this round at least considering all my recent contests

now days some cheap youtubers do live stream in between contest and give answer of the question i think codeforces should do something about it!!

If someone is honest with himself, he doesn't give a shit to them.

No, someone would give... if they won't get +ve delta bcz of them

ya thats my point because of them ranking become influated

shayan did this countless times already, so there's no point telling cf to shut him off.

Shayan, do a live stream after the contest not during the contests.

I know it's a demotivating fact that cheaters get better ranks than you. And the Codeforces team tries their best to find them. That is why the rating gets rolled back sometimes.

The thing to be mentioned should be the YouTube channel of such streamers. Not just mentioning these facts. So that all such channels get banned.

But, at the end of the day, these guys will still be there with some new idea to make others cheat.

Question: Who motivates them to do this?

It's some of us, who are lazy and greedy and want an easy way of having +delta with literally no benefit. Since they didn't improve themselves, what they did was just to make a fake image to impress someone.

Well! You said the truth. I just pondered this because the channels are rapidly increasing, and viewership is increasing day by day. I have posted a post in CodeChef. I am hoping that someone would come up with a solution.

shayan did this countless times :)))

He meant during the contest, not after the contest.

Shayan does this after the contest...not during the contest...learnt a lot from him

Disgusting. By the way, which YouTubers?

my first contest :)

Edit: Can't give it now :(

Have to go to a teacher's house to meet him. Good luck to all others tho

good luck

hoping to have fun!

It’s frustrating to see live streams sharing answers during contests. This undermines the spirit of fair competition. I hope Codeforces can address this issue to maintain the integrity of the contests.

umm, the stream starts 5 minutes after the contest, so even if you submit using the answer, it won't count to the contest submissions (or something like that idk)

many streams actually start during the contest, which can still impact the integrity of the competition. It’s crucial to address this issue to ensure a fair contest for everyone.

If you know some YT channels, it's better to mention them. So, the CF can take action against them. I think only raising the issue is not enough.

Insha Allah. Next time i’ll do that.

Please make sure NOT to mention them during the contest but after or before the contest.

Another Educational, delicious.

Good luck everyonei need to solve 4-5 problems to keep my rating :o. help.

Educational contests are so good for newbie and pupil users. I think

specialists (like me) :skull:

NO! you need to solve A B C as soon as possible!

Ali, as soon as possible was good, both of us after 1:15...

case rate (secret)

31 tir (secret)

6T(secret)

sikh(religion)tir

gesh get(secret)

sick tear

we all need it for edu rounds

Bruh, people here hate to read the whole problem statement calmly. As stated by one of our time’s finest minds, zenigata23, “why should I read the documentation while I can watch 1 second of a YouTube video, then change window again and still haven’t understood anything”.

u should stop trolling on me and get life

today please consider looking at B submissions from 38th minute many will likely have cheated solutions as again got shared in a telegram group. awoo MikeMirzayanov, i will share the links soon for many of those cheated one which already i previously mentioned in older contests.

what's wrong with D without fast io it's not getting AC

I had the same issue bye bye CM_

bye bye pupil :)

Input and output are one of the slowest parts of any program. It is good if you add fast io as a template.

In problem D, we have n, m <= 10 ^ 6, which are huge and require fast io. Another thing, is to use "\n" for the next line, don't use endl for it. Sine endl also flushes your output and is slower.

worst contest for me :( problems are good

Could someone hack my Problem B solution? The complexity is O(t*len(a)*len(b)) which is O(10^7) which should not pass but it does and I don't understand why. The system tests might be too weak (or I'm too stupid to understand why what I did works)

The idea of my code is, for each test case:

Complete source code: https://codeforces.com/contest/1989/submission/267692337

$$$10^7$$$ is supposed to be $$$0.1$$$ seconds as I estimate. Just think about $$$10^8$$$ ~ $$$1$$$ second.

Oh, I thought 10^5 operations per second was the limit in Python. Damn. Good news I guess?

Oh sorry, I didn't pay attention that you are using Python :v. So maybe I estimate it wrongly.

Well it's slower but it's probably not 1000 times slower so what you say holds

another contest of "testcaseforces"

WtF prob A?? solved B in 15 min but couldn't do A bye bye Pupil :(

same bro

if(y <= -2) pno else pyes

Basic physics. Try to divide moves in x and y. And y component you have to take care of.

can someone tell me whivh corner case Im missing in B my approach was lena+lenb-lcs . also tell me the correct approach

even i thought the same untill i thought some thing like

if a ="qwerty" b = "qwft"

then ur ans will be 7 but actual answer 8

did something like this def max_match(j): i=0 ji = j while i<len(a) and ji<len(b): if a[i]==b[ji]: ji+=1 i+=1 return ji-j for _ in range(II()): a= I() b= I() s = 0 n,m = len(a),len(b) for j in range(m): s = max(max_match(j),s)

print(n+m-s)

oh damn was upsolving this and thought exactly same. Thank you so much for the example.

i tried lcs but failed

Just brute force the sh*t out of the problem LOL(as the constraints were literally so small).

when i want to be fancy Contest make me remember "now die noob "

u cannot take LCS. think of this example string a = acdfe string b = bde

find max_lcs = max length subsequence from a which is substring in b

ans is a.size()+b.size() — max_lcs

this is didn't work I even tried with LLMS their solutions also failed

it will work see this .. 267778224

tried this during contest but got wa

Spoilerint t; cin>>t; while(t--){ string s, t; cin >> s >> t; s += '$'; t += '#'; vector<vector> dp(sz(s) + 5, vector(sz(t) + 5, 0)); int ans = 0; rep(i, sz(s)) rep(j, sz(t)) { dp[i+1][j] = max(dp[i + 1][j], dp[i][j]); dp[i][j+1] = max(dp[i][j + 1], dp[i][j]); if (s[i] == t[j]) dp[i+1][j+1] = max(dp[i + 1][j + 1], dp[i][j] + 1); // ans = max(ans, dp[i+1][j+1]); } cout << sz(s) + sz(t) — dp[i+1][j+1] — 2 << endl; }

after contest removed dp[i][j+1] and subtacted ans insetad of dp[i+1][j+1] which got accepted

How to solve C?

Use binary search on the max minimum -- the choices are predetermined unless the pairs are {1, 1} or {-1, -1}, during binary search, decide which movie to assign it to

Codeoverkill

That's way too complicated for the problem, see my submission (python) which follows roughly the same logic: all choices are predetermined except (1, 1) and (-1, -1). At last, we assign each of these a movie based on what maximizes the minimum among both movies, which can be done in O(1).

Observation 1: If $$$a[i] \ne b[i]$$$, it's always optimal to take the review of the bigger of the two.

Observation 2: If $$$a[i] = b[i]$$$, you can't greedily assign yet. However, since they are equal, you can apply this decision to either of them.

Keep track of the 1 == 1, -1 == -1, and then distribute those plus and minuses after you've totaled what you were forced to take from each in Observation 1.

I did something similar, I took the sum of both the movies in both cases and changed the sign of the review and tried to make both the sum equal. And printing the minimum of them. It gives WA, I can't find what wrong with my logic.

The main objective is making the smaller rating movie's rating as bigger as possible.At first all the 1 0 and 0 1 pairs can be counted(If 1 0 then first movie gets +1 if 0 1 then second movie gets +1) because increasing rating of a particular movie will be always good as here both smaller and greater count rating movie get positive rating.We can avoid -1 0 and 0 -1 pairs as decreasing a movie rating is not efficient at all.Then we can come to the calculation of 1 1 pairs.If already counted first movie rating is smaller then we can consider this movie otherwise the second movie will be considered.For -1 -1 pair we can always consider the movie the rating of which is greater so that it doesn't reduce the value of smaller rating movie.

Can you tell me an example test case where my code will fail. I was simply alloting the max out of a[i] and b[i], if max was -1 then allot it to the movie with higher rating and if max is 0 or 1 then allot it to the movie with lower rating. 267755402

When the ratings are the same for

`maxi = -1`

you allocate it to the first movie. This may not be optimal. For example:you should pick movie 2 for both to get ratings

`0,0`

. Instead your algorithm chooses the first movie for the first person and 1 for the second, yielding`-1,1`

.But I ran your given test case and my output was 0 for it. When after choosing -1 , we get 1 as maxi in next then I assign that 1 to the movie with the lower rating which is movie 1 bcz it has rating -1 while movie 2 has rating 0.

The problem is in some cases you're calculating -1 -1 pairs before calculating 1 0 pairs.As 1 0 pair is fixed rating increase chance for a particular movie,it should be calculated first then you can subtract always from the higher rating movie!

Can you please tell me a test case where my code is giving wrong answer.

For -1 -1 1 1 your code should give 1 but output should be 0 if you consider 2nd movie for 1st person and 2nd movie for 2nd person then 0 should be answer.

4 1 -1 -1 -1 1 1 1 1

your answer: 2 actual answer: 1

Ohh finally understood. Thanks bro.

you can distribute evenly when a[i]==b[i], otherwise maximize for rating a, b

Consider each pair of $$$(a_i, b_i)$$$. If $$$a_i \ne b_i$$$, then it's always advantageous to take the larger one, because the smaller one is either $$$0$$$ or $$$-1$$$, which does not improve the final score if chosen. The pairs $$$(a_i, b_i) = (0, 0)$$$ are meaningless, so we're left with $$$x$$$ pairs of $$$(-1, -1)$$$ and $$$y$$$ pairs of $$$(1, 1)$$$, and we want to assign those pairs to the first group and the second group, which can be done greedily.

It is so hard! I want to cry....

let's cry together

Desperately waiting for tutorial. waiting to see which test case didn't pass my sol for problem c. Argggghh!!!!!

For example, this test:

Bro can we do dp to solve C? i mean my first thought was dp then it got so confusing how to do transitions. Any help is appreciated

Maybe it's possible (it's certainly possible in $$$O(n^2)$$$) but I wouldn't think too much about it. Also read this — if the transitions become confusing, don't try to force DP on it.

Same for D.

see my submission , it's easy to understand

The contest was the best ever, but the conditions were the worst ever for me. Started 15 minutes late and got the most wrong submissions in my cf history!!! I didn't even have time to read D. I just hope don't be cyan.

I thought B was a.length() + b.length() — lcs(a, b) :skull:

Could you explain why its not?

Try this test:

1 abc adb

It's 5, not 4

damnn, thanks

consider this test case

A -> "abcd"

B -> "afd"

lcs is "ad" and you'll get 4 + 3 — 2 = 5 as answer which is wrong

same

Fuck problem A, worst A ever!

if B<-1 then NO simple observation

what's wrong in my solution in problem B? please someone help. my solution

C was easier compared to a standard div 2 but any hints for D???

Its always optimal to melt a tool after forging (gives x experience and bi additional units of that metal).

Now, if we forge ith tool

ktimes using metal j, we would use — ai+(ai-bi)+(ai-bi)...-bi =k(ai-bi)units of metal j(the last minus comes when we melt after last forging)__So for each metal, we can start forging in the increasing order of (ai-bi). Still figuring out how to bring this down from O(n*m) :(

dp the first 1e6 values, if greater then apply min(a-b) repeatedly in o(1)

I read problem D in the last minute and thought of the same thing but thought of a heap approach, like we can have a min heap for ai-bi and another max heap for metal nodes, using this the minimum ai-bi will always match with maximum metal nodes. Will this approach work? I still haven't implemented it.

no, it will tle

But why? As n,m <= 10^6, so the TC for heaps will be nlogn which i guess should come under the time constraints, i am new to CP so I don't know what the problem with this might be.

maniac_0112 can you pls tell how do you find how many weapons(i) can we make with metal(j) in O(1) so that your time complexity turns out to be O(n*m).

In order to forge k weapons,

we would need -> k*a-(k-1)*b = a + (k-1)*(a-b).

This should be less than cj (ingots of metal j). a + (k-1)*(a-b)<=cj So k <= 1 + (cj-a)/(a-b).

We can simply take the highest k = 1 + floor((cj-a)/(a-b)).

I explained my solution in this comment https://codeforces.com/blog/entry/130882?#comment-1164494

I literally complicated things too much on C by thinking of DP.

It was so simple. :(

its okay. In ranking you will see many oranges and reds also got wa on dp submission and all of them had to re-submit a non-dp solution. Very deceptive problem.

How to solve D faster than O(mn)?

You can make a dp vector of size 1e6+100 which represents the number of experience if you have i ingots. For c <=1e6 you can print the answer, otherwise you can make it smaller than 1e6 by forging and melting as much as possible with the pair that has the smallest a-b and smallest a among them. My solution: https://codeforces.com/contest/1989/submission/267753254

woaah that's a cool solution, thanks for sharing it. I was either thinking of either calculating for all 1e9 (which would TLE and MLE, ofc) or calculating for each metal by checking with each weapon all the way till it exhausts. Never thought of this holy middle way.

I still don't understand it, could you provide a detailed explanation

Firstly, if there are pairs with the same a-b, you can leave 1 pair among them with the smallest a. Then I created vector ans to make dp. The transition is: ans[i]=ans[i-v[l].first]+2; where v[l].first is a-b and l is index that i is bigger than v[l].a. You need to add 2 because you gain 2 points of experience for forging and melting the weapons.

so how could you get the v[I] which suits the requirement to do the transition?binary search?

why does official standings show div1 participants ?

yeah i was confused too

Anyone else read B as subsequence of string a and string b? Got 3 WAs and wasted 20 min because I missed that lol

Happened with me... I spent 40 minutes on B with 35 thinking about lcs due to this..Realised it very late that insertions in the resulting string could only be made at ends or the beginning so we had to check the max length of substring of b present in a as a subsequence..

Could someone hack my Problem D solution? The complexity is O(n*10^6) which should not pass but it does and I don't understand why. The system tests might be too weak (or I'm too stupid to understand why what I did works)

The idea of my code is: - Handle each c that is > 10^6 to bring it under 10^6 in O(m) - Handle them again but now that they are all under 10^6 I can use a direct access array to do memorisation. But each call to know how to bring a given int to below min(a) is O(n) so in the worst case it should be O(n*10^6)

Complete source code: https://codeforces.com/contest/1989/submission/267752822

Bringing $$$c$$$ to less than or equal to $$$10^6$$$ only takes us to choose on type of weapon with min(a[i] — b[i]), it will be O(1) for each $$$c_i$$$. Maybe the tests are weak here, as I saw that you choose it by iteration.

Exactly I chose by iteration (and i don't really know how to choose the correct one without iteration) which is why I was hackable. Do you have any hint how I could choose without iteration? I thought about doing binary search but I sorted according to a[i] — b[i] and if binary search was done it would have to be according to a sorted array on a[i]?

That's exactly what it is. Find the position $$$i$$$ such that $$$a_i$$$ is less than or equal to the current $$$c_j$$$ and $$$a_i - b_i$$$ is minimum, which can be done through binary search.

So you would need to sort on a[i]. How would you find the minimum a[i] — b[i] if it's not sorted on it? That's what confuses me :/

That's implementation issue. Create a vector of pairs, where each pair contains {$$$a_i - b_i, a_i$$$}. Sort this vector and that's what you need.

My implementation: 267751542

It is correct, i did the same thing . why do you thing worst case is n*1e6 ?

(I got hacked just now so that's a pretty good indicator of why it's not correct)

yea it's wrong. i misread your solution the first time

Done :)

Thank youuuu so much, I really appreciate it. Can you walk through how you made it? I've never hacked anyone neither did I ever hack myself so I'd like to know (both practically and how to come up with the worst case)

EDIT: also how can I see the input of your hack?

I tried to ensure you will iterate n times for every c[i], so I just generate a bunch of large b[i] and small c[i], so every c[i] will be judged n times to determine that the answer for this c[i] is 0;

hackerThanks!

anyone else thought in A that we had to collect all coins in one go?

The fact that the sample case for B is enough for us to think about LCS and got WA on test 2, interesting.

I have a feeling that a lot of cheaters are watching ind vs eng. Hence the less number of people who solved c and d.

AYO!! That's Wild

I fuck up.

bye bye Specialist QQ

OK failed to solve B :(

bye bye CM (:_;)

Wow , I solved B but failed in A

Can anyone help me with why this logic is wrong for problem C:

https://codeforces.com/contest/1989/submission/267749013

How to solve 'C'?

Greedy works well. If one of $$$a_i$$$ or $$$b_i$$$ is $$$1$$$, and the other is less than or equal to $$$0$$$, then just take $$$1$$$. For example $$$a_i = 1$$$ and $$$b_i = 0$$$ or $$$-1$$$, then we take $$$a_i$$$ because if we take $$$b_i$$$, the answer will be worse. Now we need to decide for the rest of the cases, which is $$$a_i$$$ and $$$b_i$$$ is both $$$1$$$ and $$$-1$$$. Then as we want to maximize the minimum between two types of movie, we take $$$1$$$ at the lower rated type and take $$$-1$$$ at the higher rated type.

Submission: 267713316

So if both are -1 and -1 the max(movie_a, movie_b) will take the bullet i.e (-=1) and if both are 1 and 1 the min(movie_a, movie_b) will take the cake i.e (+=1) keeping this in mind i was trying but failed, what is wrong with my approach/code : 267733477

You only said about the case when $$$a_i$$$ and $$$b_i$$$ are both $$$1$$$ or $$$-1$$$, but what about the case when $$$a_i$$$ and $$$b_i$$$ are not the same?

I'm sorry i don't even understood the problem correctly, Thnx anyway, i'll have to upsolve this now.

You can observe that in any case, instead of $$$( A[i] == B[i] )$$$, it will be known which one will be chosen, which is the option of making one of the scores increase or at least stay constant. So, you can loop over them, then calculate the score of each initially, and discard the cases of equality for now.

Then consider the cases of equality in the following way:

This approach focuses on making both scores as maximum as possible and minimizing the difference simultaneously.

Waittt, Wait, Wait "and for every person, you can choose which movie they will review" doesn't this mean movie_a += b[i] is also possible?

or i just misunderstood the question? if i did, then, I'll have to learn 'English' first LOL

for every $$$1 <= i <= n$$$, you can either choose to add $$$A[i]$$$ to MovieA or $$$B[i]$$$ to MovieB.

how to solve E? I tried many dp approaches but none worked

I used the method of generating functions to solve this problem. If the first block of identical elements in $$$a$$$ has length $$$r$$$ and the last length $$$s$$$, then $$$b$$$ will be $$$r, r-1, \dots, 1, c_1, \dots, c_q, 1, 2, \dots, s$$$, where $$$r\ge 1$$$, $$$s\ge 1$$$, $$$q\ge k-2$$$ and the $$$c_i$$$s correspond to blocks of identical elements in $$$a$$$, so they're selected from the set $$$S$$$ which contains the block $$$1$$$, the block $$$1, 1$$$, the block $$$1, 2, 1$$$, and so on. You can replace the block $$$1, 1$$$ with two blocks $$$1$$$ without changing $$$b$$$ or decreasing $$$q$$$, so you can remove the block $$$1, 1$$$ from $$$S$$$. Then there is a bijection between different $$$b$$$s and their block structures, so the answer will be (modulo $$$998244353$$$) the coefficient of $$$x^n$$$ in

where $$$f=x + x^3 / (1 - x) $$$. After a little algebra, this gives that the answer is (modulo $$$998244353$$$) the coefficient of $$$x^n$$$ in

Since $$$k$$$ is small, you can expand the numerator and denominator of this rational function and then work out the coefficients of $$$x^i$$$ in the reciprocal of the denominator one at a time, in the order of increasing $$$i$$$. After that, you just have to add a few terms together to compute the answer.

There exists a simple $$$O(NK)$$$ solution.

Imagine your original array as contiguous intervals of same values. Let's imagine the corresponding $$$b$$$ array. Let the first interval (which begins at the start of the $$$a$$$ array) be of length $$$l_1$$$, and the closing interval of length $$$l_2$$$. Now let's imagine that we are given only the $$$b$$$ array, which information about array $$$a$$$ can you infer? You will know the lengths $$$l_1$$$ and $$$l_2$$$, and you can know the lengths of contiguous intervals between them except for one case — you cannot discern a segment of length $$$2$$$ from two segments of length $$$1$$$.

As stated in previous comment, it is not useful to get one block of length $$$2$$$, so just discount that case. Now the problem is reformulated as "count number of ways to cover the array with segments, so that:

Now it is a simple dp.

Code: https://codeforces.com/contest/1989/submission/267733341

problem F is this right?:

Create an empty digraph with a unique node corresponding to every row, column.

For query $$$(x, y, c)$$$: If $$$c$$$ is red, add edge (node of column y, node of row x). Otherwise, add edge (node of row x, node of column y).

After every query, the answer is the sum of the squares of sizes of all SCCs except singletons.

Maintaining this info can be done using this radewoosh blog.

This is correct.

I am so dissapointed that I solved it just three minutes after the contest has ended, but that's part of the game...

I used this implementation to maintain SCCs.

The changes we have to make are:

Parsing the graph differently, as you mentioned.

Adding to the DSU an array that stores the size of each connected component, and updating it when merging two connected components in the DSU.

Here is my implementation: Implementation

cryforces

How to solve C by dp? I tried to calculate the answer recursively but failed to memoize it :(

c is greedy not dp.

i also start thinking about dp but simple greedy as if (1,0) =>choose 1,similar for (1,-1)=>choose 1 , if(0,-1)=>choose 0 but the cases left is just (1,1) and (-1,-1) then after that do as low and high . you can check submission 267710687

Thank you Indians for making it Cheatforces and ruining cp

bro indians are very honest, what are you saying

i can see their honesty on telegram where 1k+ indians view the solution during contest...even the group/channel owners are Indians..and they are ruining literally every coding platform ...be it leetcode ,atcoder or codeforces ..just ruining the cp environment

I am an Indian but I still very much agree with you :(

Well I mean I'm not even Indian but that's a tad racist and there is no money or whatever on the line, it's not gonna change your life if you ranked $$$i+70$$$ instead of $$$i$$$

There's always somebody bad on either side, lol.

Is this a Div 1+2 contest? Because the official ranklist is showing Div 1 members too!

In educational rounds div1 memebers without being counted as participants

Yeah, so they shouldn't be in the official preliminary standing right?

technically it is a round for everyone, but it is only rated for div 2.

In B, we only need brute force insert A to B and delete B's char existed in A, right ?

You need to find the longest substring of B in the subsequences of A

okay

Translation of problem E:

There are how many binary arrays of length n-1 with k-1 or more ones without "101" as subarray?

But how do you prove that for each such binary array there exists such $$$b$$$-array?

UPD: Yep, that works. Wow! Still wish for a proof though.

SpoilerThe actual values in the array $$$a$$$ don't matter for the distance array. What matters is which of the neighbors are equal to each other and which are different, this information is enough to locate the closest different element to every index.

So, consider an array $$$c_1, c_2, \dots, c_{n-1}$$$, where $$$c_i = 1$$$ if and only if $$$a_i$$$ is different from $$$a_{i+1}$$$. If this array has less than $$$k-1$$$ elements equal to $$$1$$$, then there are less than $$$k$$$ different elements in our original array. However, if the number of $$$c_i=1$$$ is at least $$$k-1$$$, we can construct an array $$$a$$$ where every integer from $$$1$$$ to $$$k$$$ appears at least once, since we have at least $$$k$$$ "blocks" of equal elements. That's how we get the condition that the number of $$$1$$$'s should be at least $$$k-1$$$.

The closest different elements can now be found by searching for the closest $$$c_i = 1$$$ to our element.

Now let's consider a situation when two different arrays $$$c$$$ give the same distance values. If there is an index $$$i$$$ such that $$$c_{i-1} = c_{i+1} = 1$$$ and $$$c_i = 0$$$, replacing $$$c_i$$$ with $$$1$$$ does not affect the distance array. It is quite obvious for the elements of $$$a$$$ to the left and to the right of this block, since for them, the elements we affected will never be the closest. And we can easily check that the distances to the closest different elements in our block were equal to $$$1$$$ before the change and will stay equal to $$$1$$$ after the change. So, the pattern $$$101$$$ is redundant, it can be replaced with $$$111$$$ containing more $$$1$$$'s.

Showing that this is the only redundant pattern is a bit more difficult, I will add another comment when I summarize the proof.

Proof of the last claim in the previous commentLet's show that $$$101$$$ is the only redundant pattern. Suppose there are two different arrays $$$c$$$ and $$$c'$$$ which cannot be changed into each other by replacing $$$111$$$ with $$$101$$$ or vice versa, and they yield the same distance arrays.

First, let's change every $$$101$$$ pattern to $$$111$$$ in both arrays. Now we don't have any $$$101$$$ patterns. Now, suppose we find the first index $$$j$$$ such that $$$c_j = 0$$$ and $$$c'_j = 1$$$. Since there are no patterns of the form $$$101$$$, then either this is a border position ($$$j = 1$$$ or $$$j = n-1$$$), or at least one of the neighbors of $$$c_j$$$ is $$$0$$$.

In the distance array given by $$$c'$$$, the values $$$b'_j$$$ and $$$b'_{j+1}$$$ are both $$$1$$$ (since they form the pair of adjacent different elements). But at least one of elements $$$b_j$$$ and $$$b_{j+1}$$$ for the array $$$c$$$ will be greater than $$$1$$$: if $$$j = 1$$$ or $$$c_{j-1} = 0$$$, then the $$$j$$$-th element has no neighbor different from it, so its distance to the closest different element is greater than $$$1$$$. Otherwise, the distance for the $$$(j+1)$$$-th element will be greater than $$$1$$$.

So, we have shown that the arrays $$$c$$$ and $$$c'$$$ yield different distance arrays.

Segments of size > 2 are obviously unique by the maximum number and its frequency.

isnt this enough?

I used this proof for the model approach (which is almost the same as the translation from your comment), but for some reason I thought that it's not easy to apply for the binary string version of the problem.

A detailed explanation of 267686019 of tourist for E would be much welcome. Thank you!

I consider it very educationally worthwhile to understand that code since 1) I've tried a fair bit without success 2) it was done in

`4m`

in comparison to`10m`

for jiangly and over`15m`

for a significant portion of the top contestants.This is very similar to the model solution to this problem. It will be described in the official editorial for the contest, but I can give an "early access" version of it:

SpoilerConsider a block of equal elements in $$$a$$$. If we split $$$a$$$ into such blocks, we can consider each block separately — for each element, we need only the distance to the closest border of the block (except for the first and the last block, where we consider only one border). It's quite easy to see that if the length of the block is even (let's say it's $$$2x$$$), then the distances for the elements in this block are $$$[1, 2, 3, \dots, x-1, x, x, x-1, \dots, 3, 2, 1]$$$. And if the length of the block is odd (let's say it's $$$2x-1$$$), the distances are $$$[1, 2, 3, \dots, x-1, x, x-1, \dots, 3, 2, 1]$$$. Now we don't need the actual values in $$$a$$$, we only need the information about the blocks of equal elements.

We need at least $$$k$$$ blocks of equal elements in $$$a$$$, since if the number of blocks is less than $$$k$$$, it's impossible for the array $$$a$$$ to have $$$k$$$ different values (and if there are at least $$$k$$$ blocks, it's possible to assign each block a value so that every integer from $$$1$$$ to $$$k$$$ appears). So, it looks like we need to calculate the number of ways to split the array into at least $$$k$$$ blocks.

However, this only works if there is a bijection between the ways to split the array and the resulting arrays $$$b$$$. Unfortunately, some ways to split the array might result in the same distance array: for example, the distance array $$$[1, 1, 1, 1]$$$ can be obtained either by splitting into four blocks of size $$$1$$$, or into three blocks, the middle of which has size $$$2$$$. So, if there is a block of size $$$2$$$, and it is not the first or the last block in the split, it can be replaced with two blocks of size $$$1$$$, and nothing changes (except for the number of blocks, which goes up).

Thankfully, this is the only such situation we need to handle: any block longer than $$$2$$$ can be uniquely determined by the values in the middle of it (if there is a value $$$x$$$ which is greater than both its neighbors, it is the middle of a block of size $$$2x-1$$$; and if there is a pair of values $$$x$$$ which are greater than both the value to the left and the value to the right, it is the middle of a block of size $$$2x$$$).

So, we need to count the number of ways to split the array of size $$$n$$$ into at least $$$k$$$ blocks so that only the first and the last block can have size $$$2$$$. This can be done with the following dynamic programming: let $$$dp_{i,j}$$$ be the number of ways to split the first $$$i$$$ elements into $$$j$$$ blocks.

This looks like it works in $$$O(n^3)$$$, but we can use two improvements to speed this up:

at least$$$j$$$ blocks if $$$j=k$$$;Combining these two optimizations, we get a solution in $$$O(nk)$$$.

Thank you! And for those who are interested, 267865673 is my modification such that one does a recurrence from $$$k$$$ to $$$k$$$ (in addition to also $$$k$$$ to $$$k-1$$$). In contrast, tourist went about it more indirectly via a recurrence from $$$0$$$ to $$$0$$$ (which actually made it harder to figure out what he was doing, though it is in some ways more simple).

I feel a bit bad about taking up more of your time with such a long answer. Before I posted that comment regarding the submission of tourist, I had understood the submission of neal as well as the idea behind solution.

In contrast to

as Dominater069 commented,

I felt like the idea was rather straightforward and the hard part was actually coding the dp, which involves a clever packaging and usage of a prefix sum. It was the $$$0$$$ to $$$0$$$ recurrence trick that eluded me for quite a while, and once I believed I had "deciphered" that, I set about to AC it in the aforementioned different yet similar way to confirm; only after the AC, did I see your answer. 😀

Extremely high quality problem that presumably you composed, and I am happy to give my feedback on it.

This hasn't actually taken a long time for me because, well, I just copypasted it from my editorial drafts

My translation : how many ways are there to split a segment of size n into >= k segments such that each segment (except the first and last which have no constraints on them) is not of size 2

Trivial to code a dp for this

Nvm i just notice, yours is the exact same too

Hi, can you explain the logic for your translation as well? Thanks

every segment of equal elements is uniquely identified by being like [1, 2, 3, ...., 3, 2, 1] (first and last are [1, 2, 3, ....] and [..., 3, 2, 1])

the only exception is a segment of length 2 [1, 1] which can be split into [1] + [1]. Segments of size > 2 are obviously unique by the maximum number and its frequency.

Thus, all reachable b-arrays are exactly like i stated, >= k segments constraint due to each number occuring atleast once.

Thanks

why did take this transition dp[i][j] only for j == k? Thanks;

I came out with the same translation, but i suck at dp and didnt manage to solve it:))

Interesting Problems! Without too many complex algorithms,using some basic skills to solve them is quite cool.

D timelimit is hard

problem d accepted 2 min before the contest ends, hoping to reach expert this time

Really, it was too much hard for me :)

Keep practising until it isn't.

but i need a perfect guideline to do practice. Is there anyone who will help me?

Usaco.guide

give Hints for A my thoughts on A

(Correct me ) - 1. always move along the diagonal and abs(y) should be atleast 2

In problem B, why does len(a) + len(b) — lcs(a,b)

subsequencenot work?abcd bfd The answer is 6.

no you cannot use subsequence concept of choosing in s

counter test for your logic

s="abc" and t="adbec"

according to your logic answer should be =3+5 — 3=5(wrong)

it should be 7

you can look at my submission for better clarity

hack data:

1 bdf abcdef

8(abdfcdef)

The correct sol is to find the longest substring of B in the subsequence of A

"Longest substring of B in subsequence of A" totally explained it to me.

Thanks!

If that was sarcasm, that actually does explain it exactly. You need to find the

longest substring of Bthat is also asubsequence of A. The answer would then be size(a)+(size(b)- this length). What you're finding instead is thelongest subsequence of Bthat is also asubsequence of A.problem D was great

good testing made it great tc-5 drill

Insane Div.2 !! Thanks for the authors

The problems used only basic techniques and were great!... Except for that fact that I bricked on each and every one of them T_T

Problem B (Substring and Subsequence) Video Editorial : Link : --Click_HERE

It was a massive contest !!

now way, 2 silly wrong submissions for D costed me CM

Congratulations!

Thanks pagol

can someone please have a look at my code for problem D, it's giving wa on test 11.

submission

i made a submission with code but it was wrong can anyone tell an eg where this code is failing

## include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ string a,b; cin>>a>>b; int x = 0; vector m(26); for(int i=0;i<a.size();i++){ if(a[i]>='a' && a[i]<='z'){ m[a[i]-'a'] += 1; x++; } }

}

May I know where and when the solution will be posted after the contest?

Somebody please provide a proof for A please

SpoilerIf $$$y \ge -1$$$, the coin can be caught. Otherwise, it cannot be caught.

Suppose we rephrase the problem as follows: instead of moving all coins down, we move up after each our step; we want to check which coins we can catch. Then, we cannot move lower than $$$y=-1$$$, so we cannot catch coins which start below $$$y=-1$$$.

Let's show how we catch coins which are on $$$y=-1$$$ or above. First, let's align our $$$x$$$-coordinate with the $$$x$$$-coordinate of the coin by moving either to the bottom-left or to the bottom-right. After $$$|x|$$$ seconds pass, our $$$x$$$-coordinate will be exactly $$$x$$$, and our $$$y$$$-coordinate will be $$$0$$$. Then, if we want to catch the coin in $$$y=-1$$$, we just move down; otherwise, we simply move up by $$$1$$$ step every time.

when moving up each second we will have 2 increment in y so. total y/2 + y%2 seconds required right?

Please see the D solution I think it should not give tle on test case 9 for n*logn solution

I would say putting $$$10^6$$$ element in a map would be too much, also there exist linear solution.

ya but I submitted it at 4 seconds before the contest so I couldn't optimize it

The keys of map is integer between $$$1$$$ and $$$10^6$$$, so you can just use a array to store them?

Hey, I have used the vector instead and still its giving TLE

https://codeforces.com/contest/1989/submission/267766796

this is the link to the solution. It would be great you could spare a time for it.

Pure cin/cout is slow.

Yaa, I was not aware of fast i/o. Thanks!!!

I have successfully tried 1e6 elements in a map before though. Can't exactly seem to recall the question but why exactly does it fail in this case? Codeforces judge performs about 5e7 operations per second right?

That's a rough estimation for checking whether certain complexity $$$O(f(n))$$$ would probably pass or not, but in reality, constant factor need to be considered and std::map has huge constant factor. Like, $$$O(nlgn)$$$ by fenwick tree would probably pass in 1 sec but $$$O(nlgn)$$$ by std::map won't given $$$n = 10^6$$$.

Ohhh got it. Thanks!

could somebody explain d please.

Yeah it is optimal to take A[i] minimum for a particular difference A[i]-B[i] as c[i] should be greater than A[i] and make C[i] less than A[i] with diff=A[i]-B[i]; It can be done as (C[i]-A[i])/diff<steps do steps++ as we want C[i]<A[i] and then keep the ans+=2*steps; as both melting and forging should take place make a thing such that {diff,A[i]} should be monotonically decreasing with A[i] and increasing with B[i] and remove other pairs in between them so update the dp[new_c[i]]+=dp[c[i]] as dp[c[i]] is nothing but count this can be done by two pointers simply.

queue rip

I wonder wtf a 3000+ rated problem is doing in a Div2 round.

C was easier than B.

Actually really liked the C on this one. (Not just because I was able to solve it)

why was my submission skipped during contest ????

Could the open hacking phase be extended if the queue issue won't be resolved shortly? We've already lost more than 5 hours of the phase and still have no idea when it will come back. There are many people who were trying to hack and they can't even see if their input is valid or not. I think at least a few more hours to hack should be given after the queue becomes normal again.

Now we only have less than an hour left...

I hope it doesn't end up with no response and just starting system test. Open hacking is an official phase that can affect official results, so it really shouldn't just be "whatever, nobody cares about hacks and rather wants earlier rating updates" and be wasted like this. We were announced that we will be given 12 hours, so everyone deserves to have that time as a whole and not just 2 hours.

Yeah the testcases for D seem to pretty weak as well and there are not many hacks. I am not sure if the hacking phase will be extended though.

not going to be extended. system testing has started .

I submitted a hack like 10 hours ago, and lastly when I checked after seeing your message it was still in queue, and now system test running

this is really annoying that coordinaters dont care about it :/ starting the system test after not giving a reliable chance of hacking to participants. 2 hours of hacking, 10 hours of queue

can someone explain why this code gives tle for D?

SpoilerI guess sort by a list key is slow in python. Also min is slow.

the bucket sort is kinda necessary for the soluion and i don't know how else i can do it

Using tuples as comparison key is slow. Packing the key into a single integer will usually make the code run noticeably faster. For example, try to replace

`(a[x],-b[x])`

with`(a[x] << 32) | (10 ** 6 - b[x])`

(it's easy to see this conversion keeps the sorting order).Thank you

For problem B why finding Longest Common Subsequence(len1) and Longest Common Substring(len2) and calculating answer = min((n1+n2-len1), (n1+n2-len2)) does not work?

String a needs to be a substring (so it can't be broken apart) and b needs to be a subsequence so you need to just find 1 longest subsequence and that is the longest subsequence of b inside a. Once you have it's lengh, the answer is simply len(a) + len(b) minus the length of the subsequence.

Editorial when??

I solved the problem A , and it got accepted , but now its showing that I haven't attempted it at all , its not showing up in my submissions as well. Can someone help ?

solutions are tested by system.wait for some time.

can anyone please explain why my logic for B is wrong. I am getting wrong answer in test case 578 in test 2. here is my submission-267713310

consider the test case

thanks, but i think doing abs(v[i+1]-v[i])==1 should fix the problem

it would not, consider the test case

ok understood. thanks for the help man

Can someone explain why my problem D solution failed system tests at test 14? I used DP over the starting number of ingots, sorted a[i] while "keeping b[i] aligned with it" (using pairs) and used prefix-min of a[i]-b[i] to efficiently get the best offer, and binary search to find the biggest one I can craft.

https://codeforces.com/contest/1989/submission/267730392

Problem D test cases were too weak

rating changes when?

Does anyone know, has system testing already ended?

yes

thanks

My submissions for the problem D are in queue for a long time now. Does anyone know what's happening

267829615

267824112

267822352

Update: issue got solved, got verdict wrong answer tho :(

In Problem B:

a.length + b.length — longest common subsequence

for what particular test case it will fail

abc & adc

3+3-2 = 4

Correct Ans is 6

It's $$$5$$$ actually: abcdc

oh yup

why this contest is showing unrated even i have rating less than 2100

Because it always takes a bit to update ratings even after system tests, your rating should probably be updated by today's evening

yeah thanks

That moment when you only need one more simple "idx++" line to get AC, but somehow miss it for two hours. I really didn't deserve specialist rank damn.

NOTE: To respond to this, please go to https://codeforces.com/blog/entry/130882?#comment-1164822, an identical comment located near other comments regarding problem E.A detailed explanation of 267686019 of tourist for E would be much welcome. Thank you!

I consider it very educationally worthwhile to understand that code since 1) I've tried a fair bit without success 2) it was done in

`4m`

in comparison to`10m`

for jiangly and over`15m`

for a significant portion of the top contestants.Can someone explain why only top 500 got their rating changes?

And this contest is marked as unrated for me even i'm under 2100.

Is this just a bug or it haven't been totally updated?

Thanks in advance!

Not completely updated. Happened in last contest too with second half of the ranklist