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 reel
what 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 everyone
i 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://mirror.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
int 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
overkill
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 = -1you 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 k times 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://mirror.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://mirror.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://mirror.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;
Thanks!
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://mirror.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://mirror.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.
The 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.
Let'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
4min comparison to10mfor jiangly and over15mfor 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:
Consider 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:
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
if (j == k){ dp[i][j] += psum[i - 1][j]; if (i >= 2 && i != n) dp[i][j] -= dp[i - 2][j]; }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) subsequence not 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 B that is also a subsequence of A. The answer would then be size(a)+(size(b)- this length). What you're finding instead is the longest subsequence of B that is also a subsequence 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++; } }
int ct = 0; for(int i = 0;i<b.size();i++){ if(b[i]>='a' && b[i]<='z'){ m[b[i]-'a']--; } } for(int i = 0;i<26;i++){ if(m[i]<0){ ct += abs(m[i]); } } cout<<ct+x<<endl; }}
May I know where and when the solution will be posted after the contest?
Somebody please provide a proof for A please
If $$$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://mirror.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?
I 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://mirror.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://mirror.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
4min comparison to10mfor jiangly and over15mfor 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
Do you recall how long it took to update last time?
Why am I unrated for this content? My rating has not been updated, and the contests page tells me that it is unrated for me.
Hi guys! I attended in this contest but my rating isn't changed yet, why?
I can solve Div2A easily but in div2B... I am able to think and code brute solutions but not to think of the exact solution...can anyone suggest me the direction to reach ,the level where i can solve Div2Bs
Try to upsolve after contest...and practice B from previous contests and 1000-1400 ratings problem also if you have enough solve in 800-900
thank you sir
The "good" solution is kinda brutish. Due to the small constraints you can try to find the longest SUBSTRING of b that is a SUBSEQUENCE of a and then subtract its length becuase it will be the chars that you "reuse"
need help with problem D would really appreciate if someone took time and helped . Cant wrap my head around why one solution gets AC but others are TLE.
JAVA solution TLE : 267801346 (CLEAN CODE but with java template)
C++ TLE : 267867065 (CLEAN CODE)
AC solution 267867170 (CLEAN CODE)
submitted C++ Tle Code just by adding Fast I/O and it got AC (267880403)
Nvm, a DP approach is much more efficient see here 267864529
Your C++ TLE solution doesn't have fast io.
thanks for the reply Plot_Twist and Neko1i3 , understood the reason. I also checked DP approach , will try that too although I am not pretty sure why is my approach getting AC can you tell me the exact time complexity for the approach , idk why but my intuition is saying this can be hacked if there is a case where the sorted difference of metal used and melted back increases with 1 value per index and the cost of metal used decreases with index. For such a case wont inner loop run more than logN times ?
Also I think moving back to C++ makes more sense. JAVA solution has fast I/O still got TLE. If you guys have any suggestions you're welcomed.
how to solve F?
A legit question. Is being able to solve a given problem by all the associated tagged methods or even more, a good practice? And if it is, where can I find the different ways of solutions? Thanks and regards
Hi this is the first contest I have participated in and I answered two problems correctly but it still shows unrated on my profile, does anyone know how to get a rating :(
participate in a live contest, virtual participation doesn't affect rating
I think it was, is it live as long as the hacking period hasn't ended yet? I participated yesterday when the judging system was still down.
My hacked code passes the testcases. The code gave tle during open hacking phase. But it's passing now after submitting again. In case of tle you do check multiple times about the time it takes.
So please do rejudge all solutions who got tle during open hacking phase(I mean all hacked tle solutions).
MikeMirzayanov, adedalic,BledDest,Neon, Roms, please look into once. I am sorry if I have mistakenly tagged wrong persons.
Thanks in advance:)
What is wrong in this code, Smithing Skill, Problem D ? https://mirror.codeforces.com/contest/1989/submission/267979244
I hvae not copied my solution from anywhere and what can i do if someone can think exactly like in the wat which i am thinking. The A problem was very easy so everyine can do that in same way the shortest one than it is wrong that you are blaming on me that i had done cheating. I just wanna prove that i am not guilty.Please have a look at that.
Same issues with me, if you find any way please help
Hello, I recently got skipped in all the 3 questions of this round these much days after the contest. It is really frustrating, The ID from which my code matched have written the same logic as mine but the variable namings were changed. Suppose if there is an easy and short logic to solve a code and more than one user uses it, then why should there be a plag? and there are more accounts who used the same logic as mine but they didn't got any plag? Anyone here who knows some legitimate ways to get the rating back please reply.
I am writing in response to the notice regarding my solution 267752043 for problem 1989C coinciding with solutions da.3/267750467 and daksh942/267752043. I want to clarify that I neither shared my code with anyone nor engaged in any form of cheating. I also noticed that I was the first to use this specific logic.
Additionally, I observed that the other IDs solved only the third problem, skipping the first and second, which is unusual for a participant. As I was using an online compiler, it is possible he accessed my code from there, as I noticed he had many failed attempts for that solution. Furthermore, his solution had some extra variables which I had initially included but later removed as they were unnecessary.
Educational Codeforces Round lately very difficult ):
I am writing in response to my account himanshu_2173 being blocked stating my solution 267729657 for problem 1989B coinciding with solutions vrsth___007/267686783 and bud123/267690766. I want to clarify that I neither shared my code with anyone nor engaged in any form of cheating. I am a honest CP guy being part of the platform since 2yrs.
I used optimized code using LCS which is different from other submission's logic. Looking for an early reply.
I'm scared.
Nope, we can't help you
If you want you can go alone, I can't leave my cats