Hello, Codeforces.
We are happy to invite you to Codeforces Round 892 (Div. 2), which will take place on 12.08.2023 17:35 (Московское время). All of the problems are original and were prepared by a collective of authors, consisting of kristevalex, i_love_penguins, efimovpaul and me, induk_v_tsiane. This round will be rated for participants with a rating lower than 2100.
We would like to thank:
Artyom123 for coordinating the round.
maomao90, Umi, Qwerty1232 and Mangooste for GM testing.
maks_matiupatenko, tiom4eg, ilyakrasnovv, sergeev.PRO, EJIC_B_KEDAX, Kihihihi, gmusya, zwezdinv, 74TrAkToR, Dominater069, TeaTime, antonis.white, nikuradze, satyam343, Noobish_Monk, AquaMoon, fishy15, meowcneil and green_gold_dog for Master and International Master testing.
playerr17, dmikhalin, FelixDzerzhinsky, KiruxaLight, VolkovMA, Gornak40, Splatjov, v0s7er, arseny2606, Mr_Ell, qwexd and olyazyryanova for Expert testing.
YakovLya and LinkCatList for Specialist testing.
pazal for Newbie testing.
And last but not least, MikeMirzayanov for the Codeforces platform and Polygon systems.
You will be given 6 problems and 2 hours to solve them. The score distribution is 500 — 1000 — 1250 — 1750 — 2250 — 3000.
I would like to also congratulate my cousin Max, who is turning 30 the day of the round. If you wish, you can write birthday wishes for him and I will pass them on.
UPD: Editorial
UPD 2: Congratulations to the winners!
Div. 2:
Div. 1:
As a participant I hope to get 1300+ rating or even better, Specialist
Also Happy Birthday Max, sending you best wishes
As a participant I hope to get 1800+ rating or even better, Candidate Master
Also Happy Birthday Max, sending you the best best best wishes
As a participant I just hope to get rated and nothing else
Also Happy Birthday Max, sending you best wishes
As a participant nothing worse can happen after my previous contests.
Also happy birthday Max ! Nothing cooler then having a cousin who dedicates a cf contest to you.
it can always be worse
As a participant I hope to get 1800+ rating or even better, Candidate Master
Also Happy Birthday Max, sending you the best best best wishes
why is everyone in this comments section pretending to care about Max's birthday?
As a participant, I hope to get unregister button, if I fail to get a positive delta.
Also, Happy Birthday Max, sending you best wishes
I actually do care tho
As a participant I hope to get 1700+ rating or even better, Candidate Master
Also Happy Birthday Max, sending you Best Wishes
L bro, worse happened
it's better than previous contest
As a participant I hope to get 1500+ rating or even better, Expert.
Also Happy Birthday Max, sending you the best best best wishes
As a participant I hope to get 1550+ rating or even better, Expert Also Happy Birthday Max, sending you the best best best wishes
As a participant I hope to get 1525+ rating or even better, Expert.
Also Happy Birthday Max, sending you best wishes.
As a tester I recommend you to take part in this beautiful round
You guys always say that
кшк база
As a tester, I can say that the tasks are cool and interesting
thats what they all say
As a "кошка база" I recommend you to participate in this round!
As a tester, I wish Max all the best on his birthday! Also, round is going to be fun, trust me ;)
p.s. имя нам улей
Happy birthday Max
кшк бз
Кошка база٩(๑❛ᴗ❛๑)۶
С днем рождкния, Макс!
кшк бз
Is this rated? Please dont downvote. Tomorrow is my birthday.
LOL! You were asking for downvote. Anyway, happy birthday!
As a tester good luck! You will need it
nooo I was thinking of upgrading my rating a bit :(
As not a tester good luck!
As "еритв" I also recommend you to participate in this round!
P.S. Имя нам улей
happy birthday Max
may i reach my Max rating in this contest
Lol
Happy birthday to bro Max
As a tester I recommend you to take part in this round!
Can I hope ......
Кошка база №1
as a tester, I can say that the round is interesting, I recommend participating
as an author, i recommend you this round!!
:O the author loves penguins
Wonderful portrait.
Feliz Cumpleanos Max!!! I express my deepest regrets for not being able to participate in the round for I am participating in the Teamscode competition which unfortunately has overlap w/ this round. :/ GL to everyone!!!
as someone who just saw this announcement, it might going to be a good round. GL on the round guys!
What is meant by “All of the problems are original” ?
you can't find these problems on google
In all contest problems first test by tester about 1 months before the contest then problem are approved by tester so, can't possible to find answer in google. :)
Happy birthday to Max!
dori dori dori dori
As a tester, this round isn't very good and I recommend you not to participate.
As a tester, this round is mid and I don't recommend to participate.
Happy birthday Max!!!
кшк бз
Автокомментарий: текст был обновлен пользователем induk_v_tsiane (предыдущая версия, новая версия, сравнить).
С днюхой Макс, надеюсь раунд подготовленный твоим двоюродным братом будет очень интересный!
As A participant I wish to reach Expert hopefully, and Happy 30th Birthday to Max <3
Happy Birthday Max!! Best wishes!
Happy birthday to Max!
Eat more fish and kitekat!
Although my English is not very good , help me wish him a happy birthday.
how to have huge postive delta:)
A very Happy Birthday to Max.
I hope he gets Max happiness and we all get Max positive delta so that we can have Max smile on our faces after the contest and practice at our Max level to surpass our Max rating.
As a tester I recommend you to take part in this round!
your name doesnt appears in tester's name. how are you calling yourself a tester ?
Lol he was farming upvotes
As a participant I hope to get 1200+ rating or even better, Pupil
Isn't this the same thing?
Thanks for this round and good luck to everyone!
Happy birthday Max!!
Happy Birthday Max May all your wishes come true.
Happy Birthday Max!
Thanks for this round and good luck to everyone!
as a normal person, please downvote me
Happy Birthda ，Max！
+ve contribution
As a participant i hope to get 1250+ rating . Happy birthday MAX!
Happy B-day Max
As a participant, hoping to be pupil this time. Also Happy birthday Max best wishes from my side too.
My rating decreases in div2 :(
As a participant, I hope to get a rating of 1200+ to become a pupil. Guys, please suggest ways to improve my logic-building skills.
Happy Birthday, MAX, wish you all the best in your future endeavors.
As a regular participant I hope I reach 1200+ rating...
Thanks for the round.. Looking forward to it.
As a participant, I hope to become pupil.
Also Happy Birthday Max.
Max is lucky to have a cousin like induk_v_tsiane. Happy Birthday, Max, Best wishes to you.
As a tester, I recommend everyone to participate in this round. The tasks are interesting. I wish you all good luck and positive delta.
Happy birthday, Max!
Happy birthday Max !
The score distribution is very nice and hope that the tasks are cool and interesting.
Also Happy Birthday Max, sending you best wishes <3
Mrinal_Kanti orz
Hi
I have zero experience
How can I participate in the event? Can someone help me!?
Just register for it. Keepthe score distribution in mind if you are not used to competitive programming -- first task should require just an idea, and last ones will test your understanding of data structures.
You can download carrot or cf-predictor chrome extension to see your predicted rating based on ongoing contest performance
I solved 0 problems in my first contest, btw)
How Should I register for it?
☠️☠️☠️
Happy BirthDay Max !.Wish you the best.
Happy Birthday MAX. Hope i will reach my MAX rating by participating in this contest.
Happy Birthday MAX. I wish you the best. And wish me that i can reach my MAX rating by participating in this contest.
Happy birthday to MAX!
I'm hoping for a big negative delta to celebrate my birthday too(((
Happy birthday! I hope as a gift you will get big positive delta! <3
thank you <3
Happy Birthday
Happy Birthday, Max. Best wishes to you.
Hope my fever goes down so i can participate.
Also,best wishes to Max.Have a great day.
Happy Birthday, Max!
Hope u guys have a good "fate" round.
buru nyuu
Happy birthday and all the best Max
Happy Birthday Max,sending you best wishes
I hope to get Candidate Master rank before the first day of my 3rd semester which will start 2 days after this round :)
And also.... happy birthday max ^_^
UPDATE: I failed :(
All the best to all my friends.....
Hope to solve 3 question in this contest.
Hope, this day, Max, will help everybody to reach their MAX rating)
wish u good luck and happy 30th birthday!!
as a newbie, I
Happy Birthday, Max c:
Happy Birthday Max:)
good luck & have fun
Is the rust programming language not allowed?
Happy Birthaday Max, Sending you best best best wishes
Looking forward for the contest desparately...
Also, Happy Birthday Max Tell him we sent virtual hugs :)
Happy birthday Max!
C днем рождения, Макс!
Lets Goo. My first coding contest ever. So anxious and excited at the same time
Dear Max, Warmest congratulations on your birthday! I hope this special day brings you immense joy, wonderful memories, and a year filled with success and happiness. Wishing you all the happiness your heart can hold. Warmest regards, Faizullakh, Dilettante_786
Арт прикольный
Happy birthday
Happy Birthday Max
Who is Max?
As a participant I just hope to get rated and nothing else
Also Happy Birthday Max, sending you best wishes
cogratulat_****_ions to ALL
Giving contest after long , hope to get >=0
ok
can anyone tell me, if there is any correlation between the question's score and rating? A score of 1000 means, the question is around 1000 rating difficulty level?
Rating 1000 means that a person rated 1000 has a 50% chance of solving this problem DURING the contest
No, there is no exact correlation. Sometimes the scores might be close to the problem ratings, other times they might be very different. Scores try to reflect the difficulty of the problems (higher score — harder problem; much higher score — much harder problem) but it's often difficult to accurately determine the difficulty of the problems based on the opinion of only a handful of people (problemsetters and testers).
As a participant I hope to get 1600+ rating or even better,Become first time Expert.
As a participant I hope to get 1800+ rating or even better, CM
Also Happy Birthday Max, sending you the best wishes
As a participant I hope to get 1800+ rating or even better, Candidate Master
Also Happy Birthday Max, sending you the best wishes
Candidate Master needs 1900 rating, not 1800.
Yeah, he meant either 1800+ or, better than that, become a candidate master.
Happy birthday Maximus. Also i must win 12 points to become green
HAPPY BIRTHDAY MAX!
puranyaa
Happy birthday Max, hope you will also become a top coder like your cousin.
Happy birthday Max, hope that you too become top coder like your cousin
Good luck everyone! :)
AGC Codeforces ?
Happy birthday Max
Hbd max
I love this contest. Because I will be Green!!! How I long to upgrade. TAT
It was a nice contest. Hoping to become Candidate Master in my next one. : )
Good visible tests! Really helpful. Hope pretests are good too.
-clear statement -nice problem that's a perfect contest , thanks to the organizers
How to solve C?
Believe in yourself
Write a brute force solution for small $$$n$$$ s and figure out that the optimal permutation is of form $$$1$$$ $$$2$$$ ... $$$x$$$ $$$n$$$ $$$n-1$$$ ... $$$x+1$$$.
Stupid problem
Yes, I also got accepted this way but I don't know how to prove it.
I didn't make the observation. I solved it by iterating over the max product (n^2 iterations). Then go through all n-1 remaining indices from large to small and greedily take the biggest remaining value of the permutation, such that the product is at most the max element. Total runtime is (n^3*logn). Correctness is obvious, but needed small optimizations to squeeze in time limit (used that the maximum you can get for a fixed max product is (n-1)*max product).
Segment tree for E?
SpeedforcesNot really.
It was hard D for me,but easy for others :(
Wouldn't say D was easy, it's expected complexity is around 1700.
New OEIS sequence when
Is it just me or was that round way harder than usual?
How to solve D?
Hint: Ignore a and r.
Hint2: Use merge segments.
how do I find out which is the rightmost/best segment from which to start using binary search? i am using the same idea as merge segments (storing best answer for all segments) but I am unable to find out which segment I should be choosing.
After combining the segments, x can only get into 1 segment (or not get into more than one). This is the segment you are looking for using binary search. In fact, the search can be reduced to upper_bound along the left border of the segments. After that, you take the previous one from what you found. The answer will be max(x,R) (R is the right boundary of the segment)
combining segments plus binary search
Nice contest for me, Problem Statements are clear, very close to Pupil
Nice contest, hope to become expert this round!
Hi guys, I have a question that need your help.
Example with problem B, my idea: sort all arrays (A[n]), and the result is sum of second element each array (sum (A[i][1]), 1<=i<=n) (except the min — A[i][1] with 1<=i<=n), and the min value of all elements.
I tried to solve this problem with 3 — 4 wrong times answer. In each try, I realize something, and test the output with codeforces system, when wrong, I find some test cases, realize something (or not), and solve again. So, I cannot prove some problems I solved, like problem C. What happened with me! How can I improve my algorithm?
Also HappyBirthday Max.
absolutely love the problems, thanks authors
how I solved C
too
Are there any hacks for problem F? I got Wrong Answer on Pretest 3.
wrong answer 15954th numbers differ - expected: '58', found: '60'How could I debug my code with a hack I cannot see…
I have no idea how to solve A, but I know how to solve F:
First, let's notice that we will take courses at most $$$logmaxW$$$ times because after that time spent on traversing a road will be equal to $$$1$$$. Also, all courses will be taken in the first possible city/node (to minimize time spent on the rest of the travel). I have precomputed with binary lifting:
$$$up[i][j] -$$$ $$$2^j$$$-th ancestor of node $$$i$$$
$$$cnt[i][j] -$$$ the number of nodes $$$u$$$ on path from node $$$i$$$ to the $$$2^j$$$-th ancestor of $$$i$$$ such that $$$s[u]=$$$ '$$$1$$$'
$$$sum[i][j][k] -$$$ time spent on traveling from node $$$i$$$ to $$$2^j$$$-th ancestor of $$$i$$$ if the skill is equal to $$$c=2^k$$$ all the time (without including the time needed to take that $$$k$$$ courses).
Let's define $$$f(u,v,k) -$$$ time spent on traveling from node $$$u$$$ to node $$$v$$$ if the skill is equal to $$$c=2^k$$$. This can be calculated in $$$O(logn)$$$ using arrays $$$up[i][j]$$$ and $$$sum[i][j][k]$$$.
For answering the query ($$$a,b$$$), we will find the necessary time to travel from $$$a$$$ to $$$b$$$ for every $$$k$$$ from $$$0$$$ to $$$logmaxW$$$, where $$$k$$$ will be equal to the number of taken courses. For each of the results, we need to find the first node $$$u$$$ on the path from $$$a$$$ to $$$b$$$ such that $$$s[u] =$$$ '$$$1$$$' and the closest node $$$v$$$ to $$$a$$$, but not on the path from $$$a$$$ to $$$b$$$, such that $$$s[v] =$$$ '$$$1$$$ and the result will be equal to $$$min(k \cdot T + f(a,u,0)+f(u,b,k),k \cdot T + f(a,b,k))$$$ Final result will be the minimum of this results. Overall time and memory complexity are equal to $$$O(nlognlogmaxW)$$$.
I coded it but it's WA
I now think the bug is you need to also consider nodes not on path, like a detour off the path
Yes, I think you just need to find the closest on the path and not on the path $$$u$$$ with $s[u]$='1' for every node in tree, but this can be done by DFS or again by this LCA, the point is the same.
Wait, but what if there is no node $$$u$$$ such that $$$s[u]$$$='1' on path from $$$a$$$ to $$$b$$$. Don't we need to go somewhere off path to take courses and then return?
Thanks,fixed!
This doesn't work. Consider a simple test case:
Your solution will go directly from $$$2 \rightarrow 3$$$ incurring a cost of $$$100$$$, when the optimal solution should actually be to go to $$$1$$$ first, complete courses, and then go $$$1 \rightarrow 2 \rightarrow 3$$$ with a total cost of $$$10$$$. Finding the closest course to $$$a$$$ and using it as a checkpoint is also not fully correct:
In this case, it is better to take the courses at $$$5$$$ rather than $$$7$$$, even though it is further. A full solution must take the closest detours to every vertex on the path from $$$a \rightarrow b$$$ into account, which is what gives the problem its difficulty.
I have edited my solution, so it covers that case now. It would be nice if you could read the post before replying.
The second counterexample proves that your edit is also incorrect. It would be nice if you could read the comment before replying.
Oh my bad. In that case, we can for every node remember the closest nodeand than for the path in $$$logn$$$ find optimal one or?
Yes, the key is to isolate the terms that depend on where the detour off the shortest path starts, and then find the minimum of these terms using binary lifting. Of course, there are many more details to what I've just described, but I will leave that for you to figure out.
I solved C by pre-computing and saving the answers :)
Edit: I also forgot to congratulate Max, HBD Max :D
how did you precompute values ?
By pre-precomputing them.
how did he pre-pre-precomputing them?
My question here is if he has a function that precomputes less than n^4 so he has a solution then why precomputing? :"D
you can't precompute be generating all permutations so I think he had a n^4 solution :
It was weird honestly, I thought my n^4 solution would pass, but it got TLE (maybe for like big constant or bad code).
https://codeforces.com/contest/1859/submission/218544590
You can check out my code here (I commented the code that I used to generate to maybe prevent being thought as cheating or sth like that)
Hahaha nice :"D
Congrats for ac :"D
Уже второй (!) раз не могу в последнюю минуту отправить решение: сначала кнопка "отправить" недоступна, потом -- сам кф. Это пипец какой-то. И во время контеста кнопка тоже периодически отваливается.
so disappointing when u are rank 2 15 min in the contest and now ur rank 500 at the end cuz some stupid mistakes... got a little positive delta though, nice little birthday present:P
I mistakenly read the meaning of problem B and got stuck for a long time.
Anyway, thank you for holding this high-quality round!
You thought that you can move an element only once right?
Problem A: You can just sort the array. Find the subarray starting from the first element, ensure that all elements of the subset are equal, and just print the subset. The next part will be for array C.
Problem B: Just store the first and second minimums from all arrays. Then sort the stored values. The ans will be first[0] + second [1] + second [2]... second [3]
Problem C: Create a permutation of size n. Then use a for loop. Reverse the given sorted permutation for j = i to n. Calculate and store the maximum of all n possible answers.
I hope it is helpful.
218576719 For A problem , can someone please tell me why am I getting runtime error(at pretest 1), even when this code runs fine in my sublime text.
You used b.erase(b.end());
F
Can anyone help me with what's wrong with this code for problem D? My basic idea was to sort the segments and stitch them together and finally apply a binary search for each xi to see in which stitched segment it lies.
Problem A: You can just sort the array. Find the subarray starting from the first element, ensure that all elements of the subarray are equal, and just print the subarray. The next part will be for array C.
Problem B: Just store the first and second minimums from all arrays. Then sort the stored values. The ans will be first [0] + second [1] + second [2]...+second [n-1]
Problem C: Create a permutation of size n. Then use a for loop. Reverse the given sorted permutation for j = i to n. Calculate and store the maximum of all n possible answers.
I hope it is helpful.
I have solved B with the same approach but I wasted too much time in thinking that will it be gone for TLE or not. Still confused can someone explain if will it pass or not for 1 second? if it will then how?
Hello, I would like to report an issue on question 4. Basically, I ran the code on two different online C++ compilers. For the first test case, I got the correct results on those sites. However, when I run the same exact code using CodeForces, these are the results it is giving.
I am losing my mind because I have no clue where this random large numbers are coming from in 2nd and 5th lines. Can someone either explain or if CodeForces admin thinks this is a mistake on their side, can I get the credit for the problem?
Here's my code:
This is a prime example of a VLA, which is known to be unreliable (and isn't even provided by standards), so it's a likely source of problems. Use
std::vectoror a large global array instead.The failure had nothing to do with VLA's though (see my reply to the parent comment for details).
Also, I wouldn't say that VLA's are “unreliable”. It is true that they are not part of the C++ standard, but they are supported by most compilers, including GCC which is used by CodeForces. Compilers that don't support them will give a clear compiler error instead of doing something unpredictable.
The main risk to be aware of is that VLA's are allocated on the stack instead of the heap. That's both their advantage and disadvantage. The advantage is that allocation is cheap compared to heap allocation with std::vector<>, especially for small vectors. The disadvantage is that you can overflow the stack when the array is bigger than remaining stack space. Fortunately, CodeForces uses a 256 MB stack size, so you can put a lot of data on the stack before this becomes a problem. For example, the
arrarray in this problem takes less than 2 megabytes.I would agree that in most cases using a std::vector<> is better, especially when the size of the array is likely to be large. In that case, the overhead of heap allocation is negligible.
Fair, I've just had several occasions where VLAs did seem to turn out to be the issue (well, at least replacing them would seemingly fix the problem), so I often can't help but point it out whenever I see people using them. In addition, the underlying stack manipulation (especially when used inside a loop and with several VLAs in the same frame) still seems hacky to me. However, I've also avoided e.g.
std::arrayfor a while because of a few problems some time ago, so I'm probably not the most up-to-date on what's currently broken and what is not.The problem is that
brackets.size()can be less thann, so in the bottom part of your solution you should replacenwithbrackets.size(), or you will access the brackets vector out of bounds, which gives unpredictable results.Thanks for this great round, Also Happy Birthday Max
how to solve E?
EDIT: nvm, I didn't get the problem (fortunately) :P
got A wrong thrice because i was using std::unique wrong lol :'). cost me 300 pts and couldn't finish B. sigh.
is there a way to prove and solve C without resorting to brute force with next_permutation and print? What happen if a certain language doesn't have next_permutation like C++?
If it's not easy to prove and much easier to observe by brute force then it's total BS
I took a O(n^3log(n)) approach which passed pretests in 2745ms. Out of fear of FST I then tried optimizing it without any success before deciding, "What the hell, let's just precompute all the answers".
The approach I used was to fix i and j such that p_i=j and i*j would be the maximum value of p_i * i. Then try to place the values in descending order.
Edit: it turns out my approach was actually the intended one (although I didn't manage to optimize the log factor. Maybe I was just paranoid). I suppose this shows how most people would go for a proof by AC instead of taking an approach that is much easier to verify but slower.
I'm also not a fan of problems that are of the form “brute-force some cases, spot the pattern, guess that it generalizes, and then code up the pattern”. I actually solved problem D before C because of that reason: at least problem C you could reason about.
But I don't think brute forcing permutations requires C++. Even in Python you can do it easily:
That's simple enough, and every self-respecting programmer should have Python installed.
if you don't fight for what you want Don't cry for what you lost...
Yay! Hello expert for the third time. Why is my performance so inconsistent? :(
Happy Birthaday Max, Sending you best best best wishes ,be fine for ever
speedforces A,B,C
Thanks for this great round that is full of ideas .
Автокомментарий: текст был обновлен пользователем i_love_penguins (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by i_love_penguins (previous revision, new revision, compare).
I'm new to the platform, don't know how it works completely but solution like this should be illegal right? 218544590
What's wrong with it?
might be one of the most trash solutions of A, but i solved it using scc (strong connectivity components). I built a graph where edge uv meant v % u = 0 and get all scc using Kosaraju algorithm. Then, if there is just one component, there's no solution; otherwise we can put the last component (in topological sort of condenced graph) into c-array and other components into b-array.
omg
smartest gray in the world
I was going for the same approach using dsu.... but then i thought its problem a!!
I thought those with rating above 2000 don't read whole problem and just go through the code just by reading Input/Output section. And that mistake costed me time and patience -_-
In first problem I submitted without knowing that I was supposed to print the size of array B & C (How dumb can I Be :( .. ) Still hope to get +ve delta
And can someone explain how to apply BS in D? I tried but it was too new way to implement that I failed. Please explain :)
You don't get penalty for failing example test
But late submissions gets lesser points ^_o
( That calculator looks dope. )
My idea for Problem D was to first sort the intervals, then take the union of suitable intervals and finally for each point binary search to find the correct interval. Unfortunately I needed 10 more minutes to make it work. It got accepted now: https://codeforces.com/contest/1859/submission/218580066
Thank you for this contest!
Can anyone provide their lazy segtree implementation to D?
Here
Idk what happened but it was showing failed on system test but now it's accepted. Were the solutions rejudged or something?
How did you use a lazy segtree ? What I did was processing the ranges by decreasing end and maintaining a dp which can be calculated with only a max segtree
After figuring out the answer for a portal, update it's entire range [l, r] with that.
Is there a way to solve it without lazy segtree? (not the set one though)
I solved it with "only" a max segtree.
Basically, each portal will be considered as [l, b] (because we can show it is optimal to jump on b, indeed, assume we don't, then any portal we will use to jump further than b could be used starting from b).
Consider portals by decreasing end (and also consider queries at the same time, they are just special portals [v, v], also it's important to consider portals before queries in case of equality).
Assume we know the answer for all the portals with a greater end than the current portal. Say the current portal is [l, b]. To improve our answer, we can jump on any portal [i, j] such that j > b and i <= b. The answer starting at the given portal is just the maximum of the answer of all such portals.
We can maintain it with a max segment tree. When we just computed the answer for a portal [l, b], we chmax the position l with the value b.
Now, to get the answer, we just need to query the maximum on the range [0, b].
Here is my implem: 218572801
You can solve it using dp and compressing in O((n+q) log n).
I'm honestly surprised by the amount of people who used segtree.
The constraints for problem C were too lenient. it is not difficult to find an n^2 solution
But it is difficult to prove that it's right
Is problem C pure calculations or just intuition?
I actually used a pure brute-force approach.
218562840
I don't know how my solution passed for C and D.
Can anyone please find out the problem in this code for today's B problem:
https://codeforces.com/contest/1859/submission/218573018
The solution to problem C, O(1)
cpp void solve() { int n; cin >> n; vector<int> a={0,2,7,17,35,62,100,152,219,303,406,530,678,851,1051,1280,1540,1834, 2163,2529,2934,3380,3869,4403,4985,5616,6298,7033,7823,8670,9576,10544,11575, 12671,13834,15066,16369,17745,19196,20724,22332,24021,25793,27650,29594,31627, 33751,35968,38280,40690,43199,45809,48522,51340,54265,57299,60444,63702,67075, 70565,74175,77906,81760,85739,89845,94080,98446,102945,107579,112350,117260, 122312,127507,132847,138334,143970,149757,155697,161792,168044,174455,181027, 187762,194662,201730,208967,216375,223956,231712,239645,247757,256050,264526, 273187,282035,291072,300300,309722,319339,329153,339166,349380,359797,370419, 381248,392286,403535,414997,426674,438568,450681,463015,475573,488356,501366, 514605,528075,541778,555716,569891,584305,598960,613858,629001,644391,660030, 675920,692064,708463,725119,742034,759210,776649,794353,812324,830564,849075, 867859,886918,906254,925869,945765,965944,986408,1007160,1028201,1049533,1071158, 1093078,1115295,1137811,1160628,1183748,1207173,1230905,1254946,1279298,1303963, 1328943,1354240,1379856,1405794,1432055,1458641,1485554,1512796,1540369,1568275, 1596516,1625094,1654011,1683269,1712870,1742816,1773109,1803751,1834744,1866090, 1897791,1929849,1962267,1995046,2028188,2061695,2095569,2129812,2164426,2199413, 2234775,2270514,2306632,2343131,2380013,2417280,2454934,2492977,2531411,2570238, 2609460,2649080,2689099,2729519,2770342,2811570,2853205,2895249,2937704,2980572, 3023855,3067555,3111674,3156214,3201177,3246565,3292380,3338624,3385299,3432407, 3479950,3527930,3576350,3625211,3674515,3724264,3774460,3825105,3876201,3927750, 3979754,4032215,4085135,4138516,4192360,4246669,4301445,4356690,4412406,4468595, 4525259,4582400,4640020,4698122,4756707,4815777,4875334,4935380,4995917,5056947, 5118472,5180494}; cout << a[n-1] << endl; }wtf orz you have 1000iq, I spent inf time optimising to N^3 while I could just have done this
hh, I only have O(N^3logN) solution , I don't want to find other algo ,so I try to make the tables which cost my 30 minites
This is actually quite nice. But how weird is the fact that you need to already have an O(N^3logN) solution to do this kind of stuff....
Yes, I only have O(N^3logN) solution , I don't want to find other algo ,so I try to make the tables which cost my 30 minites
Amazing contest! Problems were high-quality and fun to solve. Thanks to kristevalex, i_love_penguins, efimovpaul, induk_v_tsiane and all the other testers!
Автокомментарий: текст был обновлен пользователем i_love_penguins (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by i_love_penguins (previous revision, new revision, compare).
Nice Contest!
Happy Birthday to MAX.
Video Editorial For Problem A,B, D and C.
https://youtu.be/wxtpQIPOHgE
Also I shared how I approached C during contest and was able to pass it but was not able to prove it.
who is max? (BTW HBD max)
Hi. First of all I'd like to thanks the authors for this great round !
I got TLE on problem C (I had a badly written $$$O(N^3 log n)$$$ solution). At that time, problem C had < 500 AC.
I spent 30 minutes to optimise my solution and at that time the problem already had almost four thousand AC.
I think that it is most likely because people wrote a bruteforce and guessed the pattern from it.
I have nothing against this (because I could have done it too, guessing is a tool that anyone can use in contests).
However, I just wanted to know what people think about such problems where writing a bruteforce and guessing a pattern makes it extremely obvious. Is it okay to have such problems in rounds on a regular basis ?
I'm not even sure of my own opinion but the thing is that I feel like the proof of such a pattern is way above the scope of div2 C while guessing it is way easier. idk
1200+ Happy birthday Max<3 God bless you<3
O(n^2) solution is possible for Q3.
When I know the F was changed,I hadn't enough time to solve it.
So can this be unrated for me?
I have solved E&F after the contest.
Thanks for the nice contest ! And especially for problem D :)
I gave my first contest today, round 892 div 2 but my rating did not increase. I am able to see round 892 in unrated contest section in my profile. I was only able to solve one problem. can someone tell me why rating did not increase
Don't worry bro. It won't publish immediately after contest ends. Within one day, it gets reflected for all the participants. Welcome to the platform & All the best for upcoming journey.
oh, okay.. thanks for the best wishes.
It released just now. Congrats on your first increase.
Hello cheater pranav2401, you started cheating from first contest!!!
Thanks for great round!
constructive forces
but the problems are good.
Can problem D be solved using deque? Just like having maximum on the top of the queue..
I wrote this solution but it fails on some test cases. https://codeforces.com/contest/1859/submission/218624254
Best round I have written :)
Very nice
okay
Fancy round! Though div2C could be easily solved in about $$$O(n^2)$$$ time by iterating over every mirroring of suffix and prefix (firstly, try mirroring every suffix, then try mirroring every prefix). Indeed, such solution gets AC: 218645309.
Can you prove it?
"Max" turned 30...my rating turned 1264,30 more than my previous "Max" rating.
Happy Birthday Max. You know Max turned 30 and my rating went +30 more than my previous Max rating. Max... Max... Max... 30... 30... 30
WHO IS MAX?
Read the author's blog again☺️
happy birthday Max, I wish you all the best. also I hope to get +20 at least in this contest
I hope I can solve atleast 2 questions in this coming contest
I wanted to ask why can we sort the array in question 2 without exceeding the time limit? Wont the time complexity exceed: let sum of mi=m O(t*(mlogm))=(2.5*10^4*(5*10^4*15)) =18.75*10^9, which is a lot more than allowed time?
The sum of m_i over all testcases is ko more than 50000.
I don't think C is a good problem.Because if the intended solution in the editorial is the only solution then it's a very good prblm and a deserving way to get AC in this prblm is to go through that approach . However , if you brute force in small constraints then you find a very obvious pattern and that ruins the prblm , that is why C has got these many ACs
Hi!
We're sorry that this happened, the task was cool with the intended solution, and we felt like not a lit of people would look for the pattern, so we decided to keep it as it was.
it's ok , no need to be sorry , I know that problem-setting is a hard Job , good job on authoring the contest
please anyone explain the test case for problem E.
In problem C, if n=10, one permutation can be 1,2,3,4,5,10,9,8,7,6 so it will give ans as 305 but int the test case 303 is given. Can someone explain where I'm wrong.
Happy Birthday Max, sending you best wishes