Hello Codeforces!
On Sep/08/2022 17:35 (Moscow time) Educational Codeforces Round 135 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
UPD: Editorial is out
plz be good round plz be good round plz be good round
You can be sure that the problems will atleast be original.
lmao yes
awoo is one of the great authors , problems will be original and creative surely(in my experience).
Of course, I find educational round problems very good, however I feel like the round is a bit unbalanced
Hoping for Creative round
Educational Rounds always have original problems.
I Love Educational Rounds
Update: Although EDUs have repeated problems, still I Love Educational Rounds
I also like
bro...
that's why the title includes the word
"Educational"
Finally a Rated,Original round. Hoping for a fair and creative round.
+1
Are they all original? I don't want to waste two hours and then unrated:(
The most important thing isn't rating. It's the experience and the algorithms or approaches that matter. Only cheaters cheat themselves by their ratings, and I'm sure that you aren't that people:)
And I believe theft will disappear in Codeforces, at least in a period of time.
The least important thing is rating.
The CodeForces match basically started at 22:35 in my country and I had to stay up late for the match, so I was looking forward to the rating:(.
Then what about me?
And I believe that one who sits into midnight is more likely to pay attention to their ability, not rating:)
I totally agree with you, but I think I can go to bed early and write the next day without rating, instead of staying up late and hurting myself
That's up to you to decide:)
Great way to start long weekend. Happy moon festival to all!
I hope this won't be a waste of time.
Bro no contest is a waste of time lol
right bro,we should pay more attention to which we learn from the round but not the rating.
⣿⣿⣿⣿⣿⣿⣿⢿⠟⠛⠿⠻⠿⠿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⡿⠛⢙⣨⣥⣶⣶⣿⢿⣿⣿⣷⣦⣅⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠟⢀⡴⠟⠋⢉⣀⣠⣤⣤⣤⣀⠉⠻⣿⣧⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠁⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣷⠀⢻⣿⣇⠝⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⣼⡿⠟⠀⠙⣛⣬⠱⣿⣿⣿⣿⣿⣿ ⣿⣿⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⠿⠋⢀⠄⠁⣠⣶⣾⣿⣿⣿⡆⣼⣿⣿⣿⣿⣿ ⣿⣿⠀⣀⠙⣛⣛⣻⠛⠋⣉⣢⣤⣾⠃⣰⡄⠸⣿⣿⣿⣿⣿⣷⠘⣿⣿⣿⣿⣿ ⣿⣿⣤⢹⣷⣶⣶⣶⣾⣿⣿⣿⣿⣿⡄⠸⣷⠀⢻⣿⣿⡿⠟⠛⠡⣿⣿⣿⣿⣿ ⣿⣿⣿⠄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠄⠻⠇⢈⠁⠀⠀⠲⠠⠞⠿⣿⣿⣿⣿ ⣿⣿⣿⣷⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣶⢤⠀⠀⢲⣿⣿⣿⣷⣤⡉⣻⣿⣿ ⣿⣿⣿⣿⣧⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣳⡀⢻⣿⣿⣿⣿⣷⠐⣿⣿ ⣿⣿⣿⣿⣿⣯⡈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⡇⡆⣿⣿⣿⣿⡟⣀⣿⣿ ⣿⣿⣿⣿⣿⣿⣷⡀⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⢃⡿⠿⠛⡋⣀⣾⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣷⣀⠹⣿⣿⣿⣿⣿⣿⣿⠿⠋⢁⣠⣿⡦⠐⠀⢈⡙⢿⣿⣿ ⣿⣿⣿⣿⣿⣿⣿⣿⠋⢀⣿⣿⣿⣿⠟⢃⣤⣤⡀⠻⣿⣇⣠⣴⡿⠄⠹⣧⡸⣿ ⣿⣿⣿⣿⣿⣿⡿⠃⢠⣾⣿⣿⡿⢋⣤⣿⣿⣿⣿⣄⠈⢿⡿⠋⣠⣤⣀⠈⣡⣿ ⣿⣿⣿⠅⣀⣈⠁⣰⣿⣿⡿⠋⣤⣾⣿⣿⣿⣿⣿⣿⣷⣵⣂⣽⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣄⠘⢿⣿⣿⠟⠋⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣷⣤⣬⣅⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
Comments in codeforces..
Is it rated?
Is it original?
gl everyone. I'm sure it's original unlike the previous one ;D
Codeforces Language Picker -- chrome extension to fix codeforces language picker.
Good Luck to all Coders ! Never give up the CodeForces ! ! !
Hope to perform best in this contest
meh not so many upvotes i guess i lost my touch
Very good round ❤❤
Thanks for all the authors and testers!(✿◠‿◠).
How to solve D?
My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw.
My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)
Why did you use map? Are you trying to save memory?
Is it better to use maps instead of arrays in these type of problems?
The map is for memoization. If any recursive call revisits the same case, the map indicates what the answer is and it is immediately returned.
Without this, each step would always invoke two recursive calls until it reaches the base case, which leads to a time complexity of $$$O(2^n)$$$ (you can imagine the recursive calls forming a binary tree, with base cases as leaves, and each level removing only one character from its parent). This would get time limit exceeded. However, there are only $$$O(n^2)$$$ substrings, so those $$$(2^n)$$$ nodes involve a crapton of repeated calls to the same substrings, which can be avoided by saving the answer in a map after you compute it the first time (instead of rebuilding the same subtree every single freaking time).
This technique of "check if you solved the case before and only recurse if you didn't" is called memoization. There are other ways to achieve this, but I'm just personally comfortable with using a map for it, since it can adapt to whatever your case is described by (e.g., since Bob's case involves both Alice's character and the substring endpoints, the corresponding map also has these three parameters for the key).
Bro i know that much.
I think code looks pretty with arrays anyways your choice
(please don't assume genders)
To each their own, but I prefer maps for various reasons:
The only real downside to maps imo is that checking and retrieving values takes $$$O(\log (\text{map size}))$$$ time (as opposed to $$$O(1)$$$ time with an array), but this is generally fast enough for the vast majority of problems, especially since the map size only scales with the number of reachable scenarios.
EDIT: As later replies demonstrated, the time constraints and input sizes would not actually have accommodated the additional logarithmic factor. The acceptance of my submission was due to how successive map lookups involved keys in close proximity, so there were fewer cache misses and the worst-case runtime was not invoked as often. I would not recommend relying on this kind of approach to achieve the runtime. I do still stand by my general opinions on the advantages of maps, but I agree that its use in this particular problem is not justified due to the time complexity disadvantage.
Your condescending tone is so cute, although it is nice that you actually explained your approach.
Is it though? I'm actually very surprised that your solution did not get TLE. It sounds like almost $$$10^7$$$ operations with maps, which I wouldn't expect to fit in 5 seconds, not to say 2.
Don't be very surprised, it is actually quite easy to explain!
Maps are slow, and can't do $$$10^7$$$ random access operations in 5 seconds, because of one reason — cache misses. When you search for an element in a map, you need to look at $$$O(\log n)$$$ random memory locations, which is slow, if you haven't accessed it recently.
But if you search for an element, which is located near the element you already searched, it should work pretty fast as most memory locations of the tree path to that node should be in cache.
In the case of the Andalus's code, to calculate dp for $$$(l, r)$$$, first $$$(l+1, r)$$$ is calculated recursively, and then $$$(l, r - 1)$$$.
If you write down the actual order in which dp states are calculated, in most situations we don't go to the $$$(l+1, r)$$$ child, because it is already calculated, and just go to the $$$(l, r-1)$$$, then to $$$(l, r - 2)$$$, then to $$$(l, r - 3)$$$, and so on.
And such elements are located close to each other in the map, so access is fast.
For example, if instead of storing pair $$$(l, r)$$$ in the map, we use $$$(r, l)$$$, it gets TL: 171450551.
Or if we first calculate $$$(l, r - 1)$$$ instead of $$$(l+1, r)$$$, it also gets TL: 171451903.
What is the time complexity for this solution ?
It takes $$$O(n^2 \log n)$$$ time because there are $$$O(n^2)$$$ substrings, and we'd look for them in the map at most twice. The memoization ensures that revisiting the same case will take $$$O(\log n)$$$ time to return the past answer (saved in a map). For $$$n = 2000$$$, this is actually really risky and I would not recommend this (see other related comments for why my submission was fortunately accepted despite appearing to be too slow).
Is it not $$$\Theta\left(n^2\log n\right)$$$ due to the use of maps?
Yes, you're right, sorry about that. I'll edit it, but idk if anybody would see it. My approach was already demonstrated as being unsuitable for the time constraints, with the AC verdict being a fortunate outcome of how the specific sequence of map lookups resulted in fewer cache misses than a worst-case estimation (due to the close proximity of successive key lookups), and it is not recommended to attempt this kind of risk in general.
I agree with the assessment and would not advise anyone to follow my approach (I guess I sorta assumed that the downvotes would take care of the visibility, but that might not be the case).
I couldn't solve C, and felt its implementation would be pretty tough. This is a me issue though, great contest anyways.
how to solve C?
Hint: use a heap.
I did the following Greedy:
Pick the biggest element in each array. If they are equal, they are a match, ignore them. If they are different, apply f to the biggest one.
Keep doing until every element has a match.
This kind of simulation with a priority queue might be called a trial tree?
Use a map and compare the frequency
How did you solve C?
I maintained 2 multisets corresponding to each array, and in each iteration I compared their largest elements. If equal remove them. Otherwise replace the larger one with its reduced version, as it cannot be obtained by any other reduction.
Video Solution for Problem C. Will upload D in the morning.
Great contest. Solved till D after a long time. 499 Rank. Got stuck at E. Learnt diophantine equations mid-contest, but did not get how to answer queries in O(1).
queries in O(1) seems a little crazy, think on ternary search, to the n+1 possible ways of buying pepper
Is it ever possible for Bob to win in D? I have the conditional in my code, but I don't think it is ever actually hit.
sorry, seems like I misread the question.
String should be even as per the question.
sorry, seems like I misread the question.
baab gives me Draw on running my code
bacdmy logic was: they're all different. It doesn't matter what the first two moves are in this example cuz at the end they're gonna be two different characters and A just has to pick the smaller of the two, leaving B to pick the biggest and thus the first string is smaller
After that I sketched a proof using induction that the string HAS to be a palindrome for B to have a draw, apparently it's wrong tho LOL
aabb isn't a palindrome but is a draw. Alice and Bob both end up with ab if they play optimally.
Gives me Alice on running my code
Alice takes 'd'. Doesn't matter whether Bob takes 'b' or 'c': Alice will take 'a' and win, right?
bruh wtf, I didn't noticed it was they were prepending the char, I thought they were appending instead
Seems like no? I mean if Alice can just be greedy and pick something at least as good as Bob every step, so Bob can't win?
If the first letter and last letter are the same, Alice must take one of them while the optimal move for Bob is to take the other. If they are different, draw comes if and only if all continuous segments have a length of even, like "aabbbbaaaa". Otherwise Alice wins. Poor Bob.
Why?
I don't think that draw is iff all continues segments have even lengths. Take abccba for example, it's clear that Bob can just "mirror" the Alice's turn and therefore they end up with the same string. Did I misunderstand your condition?
Nope. If my solution is correct then he can never win since this observation is the sole basis for my solution lol
but for s="baab". bob will win. beacuse no matter which 'b' alice picks, bob will get an 'a'. right ?
The character being picked is prepended to the string, not appended. If Alice picks b and Bob picks a, then Alice picks a to get a final string of ab, leaving Bob to pick b to get a final string of ba. In this case, Alice wins.
It would actually be optimal for Bob if, after Alice picks b for the first move, Bob also picks b, so they both end up with ab, which is a draw.
In any case, it's always impossible for Bob to win if Alice plays optimally.
My answer for B, I think, is correct, but I got WA.
...that means it wasn't correct
Try $$$n = 5$$$. Your sequence generates [3, 2, 1, 4, 5]. The 3 raises $$$x$$$ to 3. The 2 resets $$$x$$$ to 0. The 1 raises $$$x$$$ to 1. The 4 raises $$$x$$$ to 5. The 5 resets $$$x$$$ to 0.
Your idea of ending with $$$(n - 1)$$$ and $$$n$$$ was correct, but what's critical is that the element before $$$(n - 1)$$$ must cause $$$x$$$ to reset to 0. If $$$x$$$ ends up increasing instead, then it's impossible for $$$x$$$ to accept both the $$$(n - 1)$$$ and $$$n$$$. Constructing the first $$$n - 2$$$ elements is the second challenge here (which is still easy, but it's not as trivial as you thought).
The hardest Div.2 round I've seen.
believe me it's not
Don't think so, at least E is easier than normal, it's pretty trivial if you know exgcd.
Probelm A.
can you please point out why this submission in wrong. 171352491
you reset the initial maximum value before the input. you'll get AC after you fix this.
Dear rezidentura, you should put ma = v[0] after the line of
cin.try reading the input before the line you give value to ma
multiplying my memory just by 2 killed me on D &_& got AC just by deleting that extra parameter
How to solve D ?
What if the importance of DP here?
dp[i][j] gives answer only for i to j part of string. 1 if Alice 2 if Bob 3 if Draw
Did you see the constraints?
Try DP!
My Submission
Always try to add explanation otherwise your comment is pointless.
You added hints but its also important to add explanation.
Can you add it in a spoiler?
Like this
... Your explanation here
My approach was just recursive DP + memoization. Make a function for Alice's turn with arguments for left index and right index of the remaining string. Make a function for Bob's turn with arguments for left index and right index of the remaining string AND the latest character that Alice picked (important for tie-breaks). Check base cases (length 2 for Alice, length 1 for Bob), check if this case was encountered before (use two maps to store results, one for Alice, one for Bob), and if neither of those hold, then recursively check the two choices (pick first or pick last character). Obviously pick the winning choice if you can, but otherwise try to force a draw.
My submission: 171425586 (sadly, it was uploading right when the timer hit 0, so it didn't count ;~;)
Why I always solved out the last problem I've tried just a minute after the ending ?
Any hints on E?
I think you may precalculate $$$dp[i] (0 \leq i \leq n)$$$, where $$$dp[i]$$$ represents the max taste you can get using $$$i$$$ red peppers and $$$n-i$$$ black peppers. The key observation is $$$dp$$$ could be decomposed into two parts, the ascending part $$$A$$$ and the descending part $$$B$$$ such that $$$A \cap B = \emptyset,\,A \cup B = \{0, 1, 2, ..., n\}, 0 \leq |A| \leq n+1, 0 \leq |B| \leq n+1$$$. For example, $$$dp$$$ could not increase, decrease, then increase. So you only have to search around the peak point.
Here is my submission: 171418858. Welcome to hack me!
Update: Hacked!
I did the same. Just use exgcd to find a particular solution so you don't get TLE, and then get it close to the peak point. My submission: 171477615.
The 171418858 is written in a hurry. After being hacked, I review my code and find it is potentially flawed. The problem lies in the following two lines:
for(; lp >= 0; lp -= xj)-- line1for(; rp <= n; rp += xj)-- line2If yj > xj, These two steps may execute up to $$$O(n)$$$ steps. So we need to swap xi and yj if yj > xj. If xj >= yj, then:
(1) line1 executes at most O(peak/xj) <= O(n/xj) steps.
(2) line1 executes at most yj <= xj steps to find a lp such that (n $$$-$$$ lp)%yj == 0.
So the complexity is min(O(n/xj), O(xj)) <= O($$$\sqrt n$$$). This is sufficient. Similar idea works for line2.
Devil is in the details. In Chinese words, 细节决定成败. I write this code really in a hurry. Reading the problem takes me too much time. Anyway, thanks hacker @robostac!
That's cool, I got it. And I think you wanted to write min(O(n/xj), O(xj)) instead of max.
Yes, typo. Exgcd is a better choice.
O(Nsqrt(N)) is not enough unless you add a lot of cutoffs, at which point it is easier to write the O(log A) per query solution and not try to fit in anything else. If anybody has a good O(sqrt(N)) solution which fits in TL, please show. I could not fit it in during the contest.
Submission
That's a cool solution! I was too lazy to precalc all factors, but that seems to be the missing part in my solution. Thank you for sharing.
I can't find a case where Bob wins. Alice always wins right?
I modified my submission to call Bob a loser if he somehow wins and it still got accepted: 171428919
So the only question is whether Alice wins or Bob forces a draw. Kinda like tic-tac-toe.
baccab
sorry ,misread the question , i thought that character should append at last
Alice picks a b. WLOG, let's assume it's the first b.
If Bob picks a b, we're at acca, which is a forced draw (identical to second test case).
If Bob picks the a instead, we're at ccab. Here, Alice can pick c. Then no matter what Bob picks next, Alice can claim the a and get a string starting with a, which will beat whatever Bob picks.
So Bob can only force a draw at best.
How many got a +1 in D because of appending and not prepending?
PS: Me even after reading that
i realised it now after trying that question for 1 hour.
Yup realized it after the end of the contest. FML :(
I got +2 for misreading the same :(
How to solve B?
you need to output the biggest two number last so you make it reset every two number For example : n=15 7 8 6 9 5 10 4 11 3 12 2 13 1 14 15
can you tell me whats wrong in my solution? https://codeforces.me/contest/1728/submission/171372656
$$$1$$$ does not forcefully reset the value, it can in fact change the value to $$$1$$$ if it is currently $$$0$$$. you need a different way.
It doesn't guarantee that the (n — 2)-th element will reset $$$x$$$ to 0. For example, consider $$$n = 6$$$, where your code generates [2, 3, 4, 1, 5, 6].
2 increases $$$x$$$ to 2.
3 increases $$$x$$$ to 5.
4 resets $$$x$$$ to 0.
1 increases $$$x$$$ to 1 (!!!)
5 increases $$$x$$$ to 6.
6 resets $$$x$$$ to 0.
You need to generate the first $$$(n - 2)$$$ elements in a more intelligent manner that guarantees that the $$$(n - 2)$$$-th element triggers a reset. Hint: handle even and odd cases separately.
Congratulations awoo with my last educational round in which I participated from any account.
Why bro? what happend?
so many constructive >:(
Just a glitch of Codeforces (
Is there something wrong with G?
I tried to hack with a testcase with $$$m=18$$$, but I received Invalid Input because it said $$$m$$$ should be in the range $$$[1,16]$$$.
Yes, there is. About 40 minutes before the contest, I've noticed that one specific version of model solution runs too close to TL, so I decided to drop the constraints to $$$16$$$, but totally forgot to update the statement. I am sorry for this issue.
Since I don't want to affect the people who got AC during the contest, I will change the problem statement, so it coincides with the validator.
In problem C In one operation,
1.pick some integer i from 1 to n;
2.assign either f(ai) to ai or f(bi) to bi.
What should I select,
only one index?
or some indices?
if it is only one index.
Then, what does it mean by some?
or Am I thinking in a wrong way?
The problem means you can do the operation as much as you want and in each time you should select only one index
if I hacked a solution and my hack was unsuccessful will my standing be down?
No, educational rounds and div3/4/5/6/7/8/9/10 rounds don't have any scoring hacking phase!
What is the test case hackers are using to break a lot of solutions on Problem C?
I want to know, too. It hack successfully to my O(n) solution.
Probably the python dictionary hack ?
https://codeforces.me/blog/entry/101817
So is the C question today again facing the dictionary hack in python that happened a few contests ago? Makes me wonder about the extent of this disadvantage for python users. BTW I guess this can be fixed by taking random XORs to reduce collisions while hashing.
How to hack hash tables and how to prevent hacks on hash tables is a very important discussion topic on Codeforces. Now that you learnt this time, you can either salt the hash or otherwise not use the hash table at all from now on.
Code is giving correct output for "ba" on local but wrong on CF. Please someone help.
https://codeforces.me/contest/1728/submission/171407603
last tells Alice made previous move on l-1(last = 0) or r+1(last = 1) or nowhere and win tells in the suffix where both alice and bob has put characters who was dominating recently
stores 0 -> loosing, 1-> winning 2 -> draw state
you should access dp after checking if l > r because r might be -1
Thanks a lot. Why the verdict wasn't Runtime error.
Out of bound is not a runtime error but undefined behavior.
Very nice problems A B C!
After looking at the solution of C, it looked pretty standard and reminded me of some greedy problems I solved some time ago. I am actually curious about the proof though.
dk if this might help but look at it this way First remove anything in a that’s in b and remove anything in b that’s in a , then turn apply operations on all number that’s greater than 9 in both a and b, let the number of operations be ans , now do the same as step one where you remove elements, now the remaining ones HAVE to be converted to 1 so just count the number of remaining number of numbers greater than 1 and add it to ans , this is your answer
yeah, I noticed this, but I am looking for a formal proof (why applying from biggest is optimal)
Hmm I’m bad at formal proofs , so , sorry , can’t help you there , maybe that’s why I’m still a pupil haha
maybe tomorrow you will become specialist
Cf predictor is saying only +30 so I doubt it , I took wayyy too long to solve A , idk I was being dumb
oh, let's look forward to the Div.3 contest coming soon then
8 months back cf-predictor always underestimated my delta but now it always overestimates it
Yea, i also feel cf predictor is giving more than actual delta nowadays. It says 15 for me i just hope its not negative at this point lol.
It doesn't have to be the biggest, but you do need to deal with multi-digit numbers before the single-digit numbers.
My approach was to first remove elements that appear in both arrays, so now the two arrays have no overlaps.
Now that there are no overlaps, we now apply the operation on every number that's $$$\geq 10$$$ (contains 2 digits or more). As proof of why this is always required, note that the values are only as high as $$$10^9$$$, so there is no number with 10 or more digits. Therefore, the operation can only produce numbers from 1 to 9. So if you have a multi-digit number $$$x$$$ in the first array while the second array has no $$$x$$$, then it's impossible to produce $$$x$$$ in the second array through operations, and it is therefore necessary to apply the operation to $$$x$$$ on the first array.
After these operations, the arrays have only one-digit numbers. We can remove overlaps once more (no operations performed) until there is no element appearing in both arrays.
At this point, we have to transform everything into 1, so we count the number of non-1s, applying that many operations to turn them all into 1, after which we are done.
Note that the operation is individual for each number and the operation will make a number smaller. So let's just consider the biggest number and assume it is in A. If there's a number in B that equals to A then alright remove them all. If not, it's clear that we should apply operations on it or we won't find a number to match it.
As for the time complexity, considering we can make all the numbers to 1, and the numbers of operations is not more than 2, so the total number is mot more than 4n.
Did you know that adding more samples is totally free?
Any hint for E? I know how to precompute the best answer for $$$i$$$ red peppers for all $$$i$$$, but I don't really know how to deal with the queries fast enough. I guess I'm missing some observation.
Probably the diophantine equations and the extended euclidean algorithm are what you are missing.
I actually knew about that but I was just thinking how should I iterate all possible solutions to find the maximum. I just noticed I only needed to check the 3 closest solutions to the global maximum since after sorting the peppers by difference, the tastiness function is a parabola.
exgcd
Is there anyone can hack my C problem?
Can you briefly describe your approach? I'm having a hard time understanding what you're doing...
Frstly,if there are some pairs of numbers which are same to each other,we could ignore them.Secondly,all the numbers'lengths are under 9,so if some numbers'lengths are beyond 9,we can only converts them into numbers beneath 9 so that they have chance to be the same to another number.
For C, what is the proof that if you have a match, you always want to pair them immediately?
Suppose you have $$$x > 1$$$ an even number of times (and you already dealt with bigger numbers). Suppose you change one of them to $$$f(x)$$$. Now the amount of $$$x$$$ would be odd, which means one $$$x$$$ would have no pair, so you must actually change both of them to $$$f(x)$$$. But both $$$f(x)$$$ are equal, so you just did two unnecessary operations, because you could just match them when they were $$$x$$$.
Can anyone please help me where I am wrong? Talking about problem C.
My submission : https://codeforces.me/contest/1728/submission/171436863
Can you please briefly describe your approach? It's hard for me to figure out exactly what you're doing.
Yeah sure
I made 2 vectors a and b initially. Then I made a vector a1 and map m1.
a1 contains elements of a that are not matching with elements of vector b. similarly m1 contains element of b that are not matching with elements of vector a.
then I iterated over a1:
let e be element of a1
then I tried finding any element in m1 that is of e length, example for e=3, I will find for any element between 1,000 and 9,999 inclusive
if any such element exist (let say we got 867) then I increased my answer by 1 (because 867 takes 1 operation to be equal to 3) and then we remove found element from the map m1.
else answer+=1 because this element is now converted to 1
lets say e=13 now firstly I calculated the digits in element e (lets name it as d)
case 1 : if d is present in map m1 then we decrease one occurrence of d in m1 and increase our answer by 1(because e is of length > 1)
case 2 : if any d digit number is present in m1 then we decrease one occurrence of that number in m1 and increase our answer by 2(because e is of length > 1 && number found in m1 is also length > 1)
else : ans+=2 because we are not able to match this element with any of the element with b and it should be made 1 for further matching.
now we iterate over remaining element in m1 (lets name this element as p)
if(p==1)continue;
if(p<=9)ans++;
else ans+=2
Code link : https://codeforces.me/contest/1728/submission/171436863 Giving WA on TC2
Revision 1 : AC now!
I think I have an $$$O(n)$$$ solution for Problem D. 171446061
If the string has following structure:
$$$ABC$$$
Where $$$AC$$$ is a palindrome and $$$B$$$ is made out of pairs of equal letters (e.g.
aahheeiiwwmmyy), then it is a draw. Else Alice wins.If the string has the structure $$$ABC$$$ then bob can always pick the same letter as Alice picked. This forces a draw.
The other direction seems not so obvious. As long as the last $$$2$$$ remaining letters are different, alice just picks the smaller one and wins. If Bob somehow forced the last $$$2$$$ letters to be identical, then alice had to pick the smaller one out of the penultimate $$$2$$$ letters, (or force the last two to be different). This reasoning can be extended I guess, but I have no formal proof.
Nice structure! I think I have some argument. Suppose we have a string of minimum length that Bob can win, denoted by a1 a2 X a3 a4. Bob must pick smaller letter than Alice at the first turn, since the best outcome afterwards is a draw. Hence, we have three posibilities:
(1) a1 > a2 and a4 > a3
i) a1 = a4
X a3 a4 must be a draw, and a1 a2 X must be a draw, so X = a4 a3 Y a2 a1. We now have that Y a2 a1 and a4 a3 Y must be draws. This repeated chain can't end, contradiction.
ii) wlog a1 > a4
a1 a2 X must be a draw, so X = Y a2 a1, where Y is a draw. Hence, when Alice pick a1 in a1 a2 Y a2 a1 a3 a4, neither a2 Y a2 a1 a3 nor Y a2 a1 a3 a4 can't be a draw, contracdiction.
(2) a1 > a4 and a4 > a3 (and thus a1 <= a2 by excluding (1)), i.e., a2 >= a1 > a4 > a3.
If Alice pick a1, Bob should choose a4. a2 X a3 must be a draw. Since a2 != a3, X = a2 Y a3 where Y is a sequence of pairs of identical letters. Now, Alice pick a4, Bob should choose a3, and a1 a2 a2 Y a3 can't be a draw, since a1 != a3.
(3) a4 > a1 so a1 > a2, which is symmetric to (2)
Great solution! Could you share your logic on deducing ABC template for draw scenarios? It took me significant amount of time to do it, perhaps your way is faster?
Bob wants to force a draw by always picking the same letter as Alice. There are only two possible answers to Alices moves. Either pick on the same side as Alice or on the other side.
In the palindrome situation Bob needs to pick always the other side as Alice did pick. In the $$$B$$$ situation Bob always needs to pick on the same side as Alice picked.
Transition from palindrome to $$$B$$$-situation works out for Bob. Transition from $$$B$$$ to palindrome does not work out. Alice can start picking on the palindrome before the $$$B$$$ part is finished, so one side of the palindrome won't be reachable. So the structure needs to be $$$ABC$$$.
I messed up this round and got a rank in the 8000s. I hope to perform well in the upcoming contests <3
In my experience, messing up in a manner that is not reflective of your skill level is usually not a problem (unless it happens a lot). Even if your rating decreases by a lot, it would quickly climb back up when you do later contests at your consistent skill level. The initial drop means you'll generally gain more rating in the next contest, so you should quickly catch up.
More importantly, I hope you actually learned more from doing the contest and improved, even if only slightly. Improving your personal skill level would eventually lead to consistently maintaining a higher rating, despite the occasional drops from randomly choking.
Nice thought! One of my problems is that I get stuck in a problem, and then struggle with it for 45 mins or even an hour. Then during upsolving I realise that the problem was not that difficult and could have solved it within 15 mins. In short, I think I can solve problems, but I take so much time that my rating doesn't increase as much as it should, or even decrease. Can you advice me on this?
Each person is different, so my advice may not necessarily be the best for you. However, my suggestion is that, when you find yourself struggling with a problem that you are able to easily upsolve later, try to think carefully about what was the crucial observation you missed that prevented you from solving it faster. I then recommend writing this down physically on paper. In my experience, this helps to avoid missing similar observations in the future.
If you find that a particular issue arises frequently for you, then make a special note of this and try to make arrangements to remind you of this for future problems, e.g., adding it to your code template as a comment, placing a sticky note on the corner of your screen, etc. Eventually, you should get the hang of dealing with these issues quickly on your own.
in problem D. if the string is baab the answer will be Bob right?? or is it a draw??
In each turn, the player add a character to the beginning of their string, not to the end. You probably miss this
Ohh shit I just wasted 5hours reading the question wrong. I was adding at the end of the string. Thanks man.
Happened to me during the contest.
Luckily, not much modification was required.
It's a draw, like following: 1. Alice chooses 'b' 2. Bob either chooses 'a' or 'b' 3. Alice choose 'a' 4. Bob choose the last one. So Alice has "ab" and Bob has "ab" or "ba", it's a draw.
It seems that Bob can't win in problem D. I got the AC during the contest but still can't come up with an elegant proof to back it up. Any suggestions?
in the test case "baab" Bob will win right??
Update : sorry i read the question wrong. Please ignore.
Nope he doesn't in this case
I had an inductive proof for that but it is too long still anyway:
Base case: we will have a string of length 2. if the characters are different Alice wins, if the characters are same we'd have a draw.
Recursive case: Suppose we have a string of length l where Bob wins. Since Alice can always pick the lesser of the first and last characters we'd skip the case where Alice and Bob pick characters from the opposite side. Consider the case where Bob and Alice pick the characters from the same side. For the recursive case we have made the assumption that Bob can't win for any string with length < l. Let the string be c1.c2.s(some string).cn-1.cn. If Bob wins then cn > cn-1 and c1.c2.s will result in a draw and c1 > c2 and s.cn-1.cn will result in a draw. Since the frequency of each character in a string which is a draw, is even, we get c1 = cn, c2 = cn-1.
Now, we have c1.c2.s.c2.c1. Since, c1.c2.s is a draw string, if Alice decides to pick c1 then, s has to end with c1. In a similar way, s also has to start with c1. We keep on repeating this process, build s and we arrive at a contradiction at a position in s.
Proof: As the length of the string is even.
The deciding factor will be the last 2 remaining characters. Now the 2characters can be same or different if different then as alice gets the first pick she wins.
If the characters are same then both of them have the same first letter in their own string. So the deciding factor will be the 2 characters picked before the last ones.
Same logic here those 2 character can be same or different if different alice wins as she gets the first pick. If same then deciding factor will be the 2characters picked just before. And this will continue. So you can see that Bob can never win.
This line of thinking is not correct. In your own testcase baab. Either way, for the first pick Alice gets to pick b and Bob gets a, though Alice wins in the end.
I just got the problem accepted. I read the question wrong and spent 5hours on the wrong question.
I was adding the characters to the end of Alice and Bobs string.
I understand the pain.
In many AC solutions I saw that people had recursions for the case where Bob wins and had print statements for Alice, Bob and Draw. But Bob doesn't win any game. So basically the cases where Bob wins are a contradiction among themselves and the code execution doesn't reach those lines.
Yours too had provisions in case Bob wins. https://codeforces.me/contest/1728/submission/171455329
Even i did the same as it is a dp solution i dont need to waste time thinking if bob can ever win. Just check all possible ways and print who ever wins. If bob can never win "Bob" will never be printed anyways.
Yepp true, I mistakenly believed that Bob can't win and ended up handling only Draws and Alice wins. It worked magically. Then I first realized I had the wrong idea which was actually correct but yeah I still don't have a more elegant proof for why.
I think you can look at a problem backwards. At last 2 letters Alice goes first and can choose lesser letter and win. So Bob can only hope for draw so last 2 letters should be the same.
It means optimal strategy for Alice is choose at any step lesser letter, strategy for Bob is to choose the same letter as Alice for getting draw.
I feel like problem can be solved in O(n) though I didn't solve it
UPD. https://codeforces.me/blog/entry/106726?#comment-951491 found comment with O(n) solution. Looks like I missed a piece of observation with combining palindromes and pairs of same letters :(
Alice is not gauranteed to have the lesser letter at each move. Consider caac
I did not say about guaranteeing. Only strategy
In problem F, how to prove that the number of useful values is $$$O(n)$$$? I've added lots of trivial optimizations but still got TLE. Or is it maybe I need a faster max flow template?
Would appreciate if Educational rounds could release the editoral soon after the contests :) Most other contests have been doing so, and I think it would help for learning about unsolved problems while it is still fresh in our minds.
Codeforces becomes Mathforces in these days
Always has been
but when i solve c2j problems i see old contest qusestion that questions are some algo orieneted but now in live contest i see questions are mainly from numbertheory
Well, math and algorithms are strongly interconnected, so there is nothing special about that. Some problems are from numbertheory, but in this round C and D were not
actually i am beginner so i am never get a opportunity to meet c and d question can u tell what topic is neccesary to become speclist ?
As I remember you can get to specialist just by solving a and b very quickly. For that just solve 800-1100 problems, they usually don't require anything hard. Might be an easy dp, but that is learnable. If you find a problem with a dp tag, just look through the code of the solution, maybe do some research on CF/Google. As for C they usually require great understanding of STL data structures and/or constructives. C is most of the time around 1500, sometimes can get up to 2000, but that's a rare thing, and usually has such high rating because of a cringy solution. That's mostly it for the specialist
I'm a newcomer in Codeforces.That's my 5th contest... But i have noticed it takes really long to update ratings on codeforces.. Why is it so?
Because of the open-hack phase, it is for Edu and Div 3 (maybe also 4) rounds, lasts 12 or 24 hours. That's the main reason why it took so long
Hey, Can you give me some guidance on how you reached expert so quickly..?
I'm an 8 grader who learns AnDS in different school clubs + actively solving CF problems on different topics, also try CF EDU
https://www.youtube.com/c/pavelmavrin this channel is cool.
And finally I think there should be a website where there are most of the topics for CP
Is my Solution to A good? I feel like I wasted time to write such a solution, and could have written a much simpler solution in less time.
https://codeforces.me/contest/1728/submission/171356537
Yeah!, just print the index of highest element.
Shit that was easy. Thanks
why are ratings still not published, is this round rated or unrated?
Edu round take time to update rating
How long usually ? And why? Why different times to update ratings for different types of rounds ?
There is no fix timing but it take long to update rating, the reason is after hacking phase they add hack test cases to thier test case file and then multiple times system testing
Because there is the 12 hour hacking phase and after that all the solutions need to be re-judged on the successful hack testcases. Oh and also Mike needs some rest too :)
Via debugging E, I'm surprised to find out that -54/15=-3 (in c++) and -54//15=-4 (in py)
When will the rating update?I cant wait to get a positive result.
Become specialist.Winwinwin!
If I solve any question even though I am div 4, will my rating go up??
I think you will gain rating.It is easy to gain rating in your first six contest.
I completed 2 problems in yesterday's contest still i am unrated. When does it gets updated?
When will the ratings get updated and tutorial get released for this round?
Why rating hadn’t changed yet isn’t it supposed to be after 2 or 3 hours just after open hacking phase?
I have read the problem B. It's clean but i can't solve. Help me! p/s: i just have solve as brute force thank you
ok here is the idea u will notice that you can at most get the sum of the two largest numbers in the sequence that because each two consecutive positive integers must be greater than to the following number to them this is the case for n > 3 so if i give you n = 5 then max you can get is 4 + 5 which equals nine and if n = 8 then the result will be 7 + 8 and so on the problem comes is that how i make sure that when i start to count the two largest numbers the current res is 0 so if it is even n like this case n = 6 then the sequence will be like 4 3 2 1 5 6 which if you trace will get 0 4 0 2 0 5 11 so if it is even print from n-2 to 1 then print n-1 and n if n is odd like n = 7 then just replace n-2 with n-3 so it will be like that 4 5 3 2 1 6 7 which by tracing gives 0 4 9 0 2 0 6 13 and you can generalize this on any n.
when will be the rating changes?
uhh... when will the rating update?
why haven't the rating changes appeared yet?
I guess the rating will be updated after the #820 starts to register to prevent some bugs of rating calculation.
Why is my code giving tle on problem C(digital algorithm) using unordered_map but getting ac using map?
Anti-Hashing Hacks
Check this out for more.
Tip: Always try to avoid unordered_map
My intuitive reasoning to D :
First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.
The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :
For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : $$$aa \rightarrow aabb, bbaa$$$ or $$$baab$$$)
The critical point is that if we add to the different side, we can't add to same side anymore. Take the example $$$baab \rightarrow baabcc$$$, here Alice can take $$$b$$$ and Bob can't take any $$$b$$$ so he will lose
So the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome
In problem D why using global recursive function link gives AC whereas converting it into a recursive lambda link is giving MLE ?
define int long long? Please comment this line and test it again yourself.
Oh, thanks!! I never thought this line could be nasty.
Hey everyone... is this round rated? I don't see my rating changes for 1 day (mostly, it takes under 1 day) so I just ask in curious.
Yep, the round is rated, system testing has been done few minutes ago we may expect rating change soon!
Can anyone explain me non-dp (greedy) solution for D? i.e. $$$O(n)$$$ solution?
You can get an inductive/recursive proof for the type of string, once you get that code is fairly simple.
You can uses the below steps as hints/ideas. First see the answers for n=2, n=4; try to see observations.
Note that Bob never wins, use induction to prove it.
Try and go recursively, note that after both players make 1 move, there are only 3 possible strings that be the remaining string.
Note that a palindromic string = Draw, furthermore, if s[0]=s[n-1], and the substring in between them is a string that gets a Draw, then Bob gets a draw. This is one type of solution.
If s[0]!=s[n-1], there is only one way Bob can get a draw, s[0]=s[1] and s[n-1]=s[n-2], with remaining substrings in both cases must get draw for bob.
Use observations in hint 4 to prove that s[2]=s[3], s[n-3]=s[n-4], and similarly s[4]=s[5], s[6]=s[7] and so on. This is second type of solution.
Combine both types of solutions and you will get the criteria for strings where Bob can get a draw, its easy to see confirm that Bob will always manage to get a draw in this.
If the string s is of the kind s = (a1,a2,...,a(n-1),an), then if for some 0<=k<=n, ai = a(n+1-i) for all 1<=i<=K, and a(k+1)=a(k+2), a(k+3)=a(k+4),..,a(n-k-1)=a(n-k), then the answer is a draw, otherwise Alice wins.
Link to the code: https://codeforces.me/contest/1728/submission/171419727.
https://codeforces.me/contest/1728/submission/171513494
https://codeforces.me/contest/1728/submission/171383658
Does that small change actually speed it up by that much?
What exactly is the meaningful change? It's hard to tell with how you also adjusted indentation and brackets and such
Oh it's because I used .count() which can be O(n) worst case.
Uhh, I think .count() on a map would have runtime logarithmic to the size of the map, in the worst-case. If that's the only change, I'd be surprised if that led to the time limit exceeding. Then again, I suppose the check happens quite a lot in here...
Nah I used count on a multisrt
Why did you skip my d? Do we have to ask everyone to use different ideas to solve the same problem? I don't understand
Because 171399055 vs 171411235.
https://codeforces.me/contest/1728/submission/171413965 https://codeforces.me/contest/1728/submission/171404066 can you tell me why my code skipped look at my code it OBVIOUSLY not the same plz look at the two codes MikeMirzayanov
Absolutely same. Just stop cheating.
True. Trickster_001 you just changed the variable names and thought that you are clever enough, but the Codeforces cheater-catching machine outsmarted you.
can you tell me when will the rating be updated, please.
Hello mike, sorry to bother you here, can you please take a look at this aswell link
Why the rating hasn't been updated yet!?(┬┬﹏┬┬) MikeMirzayanov
and where is the editorial? ◑﹏◐
Thanks , the rating is now changed !!❤
Hey, yesterday I had 3 accepted solutions and today I have only two. I've got TLE on this submission: 171386970
Is it an error or is my solution bad?
Can I download a test to check on my own?
TLE because you used unordered_map, which can be hacked using anti-hashing. Just use map instead and try again.
Oh, thanks. I didn't know that.
Check this link for more.
I think you can see the test cases for every submit now. Just look for "link" in bottom left corner of you submission link
I can see a "Click to see test details" but there are only like 70 of 200000 numbers followed by ellipsis in the test input. Am I missing anything?
Oh no, my bad. You can't download the tests it seems. But even if you download I don't know how would you evaluate TLEs. Do you know some hacks for it?
What do you mean by "evaluate TLE"? I would have executed my program and typed in the test. 2 seconds is a lot for a program that was supposed to be O(n) time complexity. Earlier, I thought I got TLE due to, for example, a lag of the CodeForces server.
I mean the server running the tests might be having different configurations than your personal computer. So I was curious to know how would you identify TLEs because of this configuration changes.
But surely O(n) solution should take less time than 2 seconds unless the built-in libraries used take O(n)
As far as I know, the configuration of compiler is available here. I'm not sure if there is no newer one.
Hi, MikeMirzayanov.
The submission 171396201 and 171412747 of 1728D - Letter Picking are just coincidences
I am sure I didn't copy the code or send it to others.
Obviously, we have the same idea of this problem, and coincidentally, our code styles are similar.
My submission is at 23:33(UTC+8) and the other one's submission is at 00:09(UTC+8). And this problem is simple for me. This ruled out the possibility that I copied his code.
By the time he submitted his code, I had already came up with the solution to 1728E, so I am sure I can become yellow after this contest. I have no reason to send my code to others and cause me to be skipped.
Moreover, solutions to 1728D are all very similar, except dfs and the O(n) solution. If necessary, I can find more submissions similar to mine.
So I just have the same idea and similar code style with a stranger coincidentally.
Thanks!
dont worry i had the same
he just ranomly does this to take the piss out of us at this point :|
sad:(
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
How to become pupil as soon as what topic really need to solve 1000 1100 and 1200 1300 rated problem ?
I am finally an expert. Thanks to this contest :)
Can someone explain digital logarithm to me? I just don't understand what "f(x) for a positive integer x as the length of the base-10 representation of x without leading zeros" means. In example 2 why does f(2) = 1? and f(100) = 3?
f(100)=3 because 100 has 3 digits.
It's a great competition.I like it very much.
trash