Hello, Codeforces! Or, as we like to say in Romania: Dacă voi nu mă vreți, eu vă vreu, Codeforces!
I am glad to finally invite you to participate in Codeforces Round 915 (Div. 2), which will start on Dec/16/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
The problems were supposed to be authored and prepared by cadmiumky, but in reality they were by tibinyte.
I would like to thank:
Say_my_name for LGM testing
- cristi_tanase, Gheal, andrei_boaca,
Andreasyan, eggag32, wavelets, Riblji_Keksic, htetgm, rolandpetrean, Lotomba, Dominater069, enigma.cpp, FairyWinx, wuhudsm for all being phenomenal testers in equal measure.
- freak93 for TBD.
- MikeMirzayanov for great platforms, codeforces and polygon!
Scoring Distribution: 500-1000-1500-2000-2250-2250
The problemsetters wish you good luck & have fun :)
Editorial is available here.
Dominater069 orz
what was your contri in the round
Posting the announcement.
And the editorial.
Thank you sir intrusiv for teaching us what recherché means.
Now can you please tell me that what freak93 did ??
what's TBD ?
To Be Decided
To be determined
freak93 for To be determined ?
yeah it's similar to a joke I guess
To be declared.
As a tester, the round is very nice and I wish you all to solve everything you can and get a high rating!!!
Hope to become Expert in this round
Best of luck. I hope to become master this round
hope to solve E on this round
Another newbie tester?
newbie problem setter 😱
Why does it tell you a cheater when I hover your handle?
https://codeforces.me/blog/entry/115895
Будет круто, если я получу специалиста в этом раунде..)))
Hope I will be Legandary Grandmaster after this round !
How to become purple? i think i can solve E after the contest,but when i solve D ,100 minutes has been used ,so i dont have enough time
Excited for the round ?
Are tibinyte2006 and cadmiumky the same person ??
Yes, we
are the same
person indeed
very
observant
cf contests >>> university exam prep
As a tester, I really liked the problems, and I hope that you will like them too
Does it rate?
TBD
Hope to be a Master this round!
Hope to become pupil this time!!!
Hope to get to -39 rating after this round!!!!!
Geothermal will win Codeforces Round 915 (Div. 2)
wait till the God Comes...
Name starts with T, and ends with T.
is it rated?
STORY OF MY LIFE:
Day After Day, Inconsistency after incosistency,
Yet here I come, to solve another 3 problems and then get stuck at 4th, getting angry at problem setter for not explaining problem statement clearly, and in the end realising my own mistake and succumbing to my own dumbness and accepting that I am not made for this...
Till next time... ( Yet here I come, to solve another 3 .... )
Interesting score distribution; Looking forward to the round!
What's exciting about this?
E/F not really being much higher than D
win114514 ORZ
Possibly the highest gain from a Div. 2 contest — rank 1 (barring FST) with prior rating: 2099
Edit: Apparently not anymore.
How to solve D?
$$$MEX(a_1, \ldots, a_i) = min(a_{i+1}, \ldots, a_n)$$$ for permutations, therefore sum of prefix mexs == sum of suffix mins. After this observation problem is pretty standard, iterating over all cyclic shifts and recalculating cost in some way
Ahh yes you are right
Thanks for your answer
lmao, had the observation but had no idea how to do the rest...
sevlll777 I approached it this way, please tell me if im wrong: I took some example permutations and got to a conclusion that the function for sum of cyclically shifted permutations is bitonic (increases, attains peak value and then decreases back) hence i tried to find that point using binary search but it gave WA on test 2.
I think people mention that the result is not convex (could increase and decrease multiple time), so it probably won't work
I just found a tc where it failed, my bad!
The way I solved it was to look from the end rather than the beginning — then the sum of MEXs is related to the sum of suffix minimums.
Then I split the problem into two sub-problems: if you cut the array at a certain index and then swap the two parts obtained you get a cyclic shift. I solved the problem separately on those two parts. I did it in a very convoluted way with monotonic stack + binary search on a bunch of arrays but there is surely a better way.
Segment Trees worked for me. Basically, found all initial mexes, and then, did cyclic shift one element at a time, calculating the updated mexes. So what should happen when removing a[I] from the start of the array is considered. All mexes greater than a[I] will fall to a[I], also, adding a[I] to the end again simply adds n to the mexes. This is just done for all I from 0 to n-1
Another approach: compute mex values for the array, and encode them using run-length-encoding:
RLE = [(mex1, cnt_mex1), (mex2, cnt_mex2), ...]. This array will have increasing sequence of mex values. Then you can implement left cycle operation: it will remove some of mex values from the end of RLE, and add two more values:[(x, removed_length), (n, 1)]. Doing so you can also keep total sum of mexes in the RLE. It is possible to show that such implementation gives linear complexity: https://codeforces.me/contest/1905/submission/237518768Why O(n) didn't work for C ?
It's working. I think you're just wrong in your estimate of the asymptotic
Is cost function in D convex by any chance? I guess it's really not, binary/ternary search shenanigans were my last hope anyway.
A and B were almost too easy, difficulty of C was sensible, then it's just pondering problem D for the rest of the remaining time.
No.
why trying to kill nlogn in D?
cool contest, although it felt like you should try to solve both D&E, but have too little time, 2 hrs 15 min would be better
how to solve E can anybody please tell? i think i got it at the end but im not sure
A $$$O(n)$$$ solution would be simulating the whole segment tree process, adding $$$v \times (2^\text{No. of leaves in left subtree} - 1) \times (2^\text{No. of leaves in right subtree} - 1)$$$ to the answer each time.
By trying some smaller cases, you may observe that at each depth, the maximum difference of the range that the node represents are at most 1. So, for each depth, you can group the nodes into at most 2 sets, and then you can quickly calculate the contribution of each set of nodes to the answer (in $$$O(1)$$$ time complexity). The final time complexity would then be $$$O(log N)$$$.
thank you!
Problem A looks like John Conway's Game of Life.
Segment trees are not ugly, segment trees are poetic.
Probably overcomplicated B, but here's my thought process:
Remembered about the Tree = edges of a diameter + forest representation from TheScrasse blog. Then, if you visualize the tree as forests hanging on the diameter, you can see that no matter how the diameter is computed, after each operation, the number of leaves reduces by 2. Hence, answer is $$$ceil(leaves/2)$$$.
Submission
Do we need to remove diameter leaves? I think it's ok to choose any pair of leaves, i might be wrong thou. I'm just asking
If you do a random merge:
But, it can be done in $$$ceil(5/2) = 3$$$ steps. The catch here is to avoid creation of leaf nodes after merging, unless absolutely necessary (for example, when there's a single forest hanging on the diameter, except for this case, in all other cases, you can guarantee that if there are atleast 2 forest, leaf node counts will go down by 2).
No, I think if you take any leaves at random, try taking adjacent leaves for Balanced BST
B?
ceil(leaves/2)
count the root too if it has one edge. (I usually never call a root a leaf).
Ans --> ceil((single edge nodes)/2)
Here is my screencast of solving all problems in the contest (HD will be available once YouTube completes processing)
I will also discuss how I solved all the problems in the post-contest discussion stream.
Do we needed tree/graph knowledge to solve B or do there was any other way to solve it.
Not really, you only needed to know what is a tree and adjacency list representation of the graph.
How come the answer for B isn't just the ceiling of the number of leaves divided by 2?
It is?
Edit: I can't view your submission at the moment. But maybe you're calculating the number of leaves by DFS, which will disregard the root.
not only leaves, all the nodes connected by only one edge, that means, if the root is have only 1 edge, it will be counted too.
that's the answer. You used "tree[v].size() == 0" to find leafs. it will be tree[v].size() == 1
Ah I see! I made the mistake of treating this tree as directed. Thank you so much!
C >>> B for me can someone please explain how to solve c?
lets say the largest subsequence is zzba in the first iteration,then in the second iteration will be zzb, because after one right shift it becomes azzb,so now we cant take 'a' in the largest subsequence, this observation is very useful in solving this problem
guys why was my code outputing 1 less than the answer in B
ll t[maxn];
void run(){ ll n; cin >> n; for(int i =0 ; i < n; i++) t[i] = 0; for(int i =0; i<n-1; i++){ ll v,u; cin >> u >> v; t[v]++; t[u]++; } sort(t,t+n); reverse(t,t+n); ll c = 0; for(int i = 0; i < n; i++){ if (t[i] == 1) c++; } cout << (c+1)/2 << nl; }
nodes are numbered from 1 to N but you are iterating from 0 to N — 1 either iterate from 1 to N or decrement u and v by 1
Thx, yeah I'm so maddd
if it wasn't for this I would have solved to C
A strange distribution of complexity. A very simple C, and a complex D for such a C.
Anyway, if someone solve D, how?
Sorry I don't think C is easy, it's hard.
I think this is a trivial problem, just do what you are asked to do. According to clist it about *1300 problem
let $$$mx_i$$$ be the highest index $$$j$$$ (0 based) such that $$$p_j \leq p_i$$$.
Then the cost is $$$n^2 - \sum_{i=0}^{n-1} mx_i$$$.
We can simulate cyclic shifting using a sum-segment tree that supports adding a number and assigning a value to a segment.
See my code for more details: 237511939
C (40+min) is harder to debug than D(20+min).... Because I misread it as substring lol.
And I solve them using the same algorithm using the decreasing stack. For C it's to find a largest subseq, for D it's to find the min value on the right.
For D, you can start with x x x x x x x 0 and then start to put numbers from left to the right. The mex of the new moved number is the min(moved number). Using a decreasing stack can maintain the count simply.
Hoping to become Pupil in this contest :)
Need a treat :)
How to solve C?!
notice that the largest lexicographical subsequence after all the moves will get reversed (because it will be non increasing so doing the operation until it gets reversed is optima)
so just reverse it and check if the string is sorted or no
and the answer is (size of the subsequence) — (the frequency of the first element in it)
you subtract the frequency of the first element because there's no need to shift the because the elements behind it will all come in front of it
here's my submission
I confirmed with author that "sorted state" means "non-decreasing" close to the end...and i was trying to debug C for over an hour just because I output 0 instantly if the given array is non-increasing...
Shouldn't "sorted" be more clarified in statement?
has anyone tried dp on problem D? for two different cases: i < index[0] and i> index[0]?
Operation "Problem A" Struggle Report
Hour 0: Entered the battlefield with confidence, assuming an easy victory.
Hour 2: Reality check. Explored different algorithmic approaches to tackle unexpected challenges.
Hour 5: Delved into online forums, particularly Stack Overflow, seeking insights from cryptic responses.
Hour 8: Consulted textbooks, tutorials, and documentation in a desperate quest for understanding, attempting to reshape the problem into familiar forms.
Hour 12: Embraced creative madness, resulting in a code resembling an abstract art piece – a chaotic masterpiece born from unconventional solutions.
Hour 15: Faced a low point but chose resilience. Rewrote code, refactored, and debugged tirelessly.
Hour 18: Pieced together fragments of wisdom, forming a makeshift strategy. The problem, once formidable, started yielding to relentless effort.
Hour 20: Eureka! A breakthrough moment! The culmination of struggle, frustration, and experimentation led to a working solution. Celebrated the hard-fought victory.
Verdict: The journey through the Problem A labyrinth was a relentless pursuit. From conventional to chaotic, desperate to creative, every avenue was explored. In the end, triumph emerged from the crucible of hardship. To fellow warriors: persevere, adapt, and conquer! #ProblemAStruggle #CodeWarriorPersistence
Yes, I love you too;
C is too hard for me. RIP my rating
try again next round
same. Smh got WA on second pretest twice, wasted 2 hours on that problem
by the way, any ideas why it fails? 237512765
I don't know why it fails, but I tried with the test I found my solution failed with and it turned out yours failed too.
The answer is 2, and your solution says 1.
Did "D" literally 10 seconds after the contest :").
been there... wish I didn't search for that bottle of water.
AHHH Why can't my segment tree pass problem D
Consider deleting the beginning of the sequence and placing it at the end of the sequence. The deletion of $$$x$$$ is equivalent to taking the minimum value of a certain suffix and $$$x$$$ in the mex sequence, while insertion only requires adding $$$n$$$ at the end of the mex sequence. Simulate this process using a segment tree. We can find the beginning of the suffix using binary search on the segment tree, then modify the interval, and finally sum the intervals to calculate the answer. Complexity $$$O(n \log n)$$$. In the code, I stored the mex sequence at positions $$$2$$$ to $$$2n+1$$$.
It seems they intentionally failed segment tree solutions.
237512862 mine using atcoder library passed.
Lazy Segment tree is too slow. You need to use stack to keep track of the sum of suffix minimums. It's possibly to remove element from this stack when sliding in O(log n) using binary search and some tricks (I did this, it passed as bin search is much faster than lazy segtree) but it turns out it isn't needed. Because the biggest suffix will always have 0 as minimum which doesn't contribute to the sum.
My nlognlogn solution with lazy segtree + bsearch passed in C++ 20 somehow but not in C++ 17.
This is the 4th Div. 2 in a row I solve the first 3 problems, any advice to start solving D's ?
Convert it into another problem. We want the n + (maximum possible sum of (minimum suffix array) over all possible arrays from shifting)
Stuck at 3 problems as well. For me, if D is some math issue that I cannot solve even if I have 24h, then I will let it go. If it's something just related to the algorithm, I will spend more time to upsolve it after the contest. By shortening the solve time, I can sometimes finish D now.
can someone please explain how B is ceil(leaves/2)?
You can take a path and compress it every move. Compressing a path removes 2 leaves.
Actually when you have 3 leaves, you can at most remove 1 leaf in one operation.
we select 2 leaves every operation
choking on B by thinking about diameter of the tree :v
You really couldn't come up with a name for problem F, could you?
does anyone use segment tree for problem D?
I did: 237526207. A little bit tight on TL, but works
Just a heads up: Is it allowed to compress the code and execute it to make it difficult to hack? Example submission Last line is the obfuscated code: exec(decompress(b'\x1f\x8b\x08\x00s\xc2}e\x02\xff..')
See codeforeces rule
Solution code obfuscation and creation of obstacles to reading and understanding the solution is prohibited. It is forbidden to use any special techniques designed to complicate the reading of the code, to understand its workflow.
Any idea why this fails for C?
Also, todays ABC C and CF B are kinda same, there you remove nodes, here you remove paths of nodes.
It fails on this test:
The answer should be 2.
Thanks a lot! It passed now.
Man, I'm so sad. I got the solution for this problem and fully wrote the code when there were only 500 solves. And then spent the entire time trying to figure out the mistake but I couldn't. Another day of losing rating :(
I'm sorry for you, I know how it is, it happened to me. But look at the good part: Div.3 in 3 days! You can get more rating there :)
Excellent problems!
I advise the authors to study what segment tree are, because they don’t know
ooops, maybe I never become pupil! only two solves!
How to solve C?
Part 1 : Finding the lexicographically largest substring.
Hint : If you iterate end to start and maintain a char (largest so far), and if current char is largest, include it.
Part 2 : Note that only these characters (or a subset of them) are part of every move Hint : Every time the set reduces by exactly one character
Part 3 : You observe that the set of characters selected in 1 will eventually be reversed.
Part 4 : Can you construct a string where (step 3 is fulfilled)
Part 5 : check if string is sorted.
Nice Move ? : Intentionally left one edge case for you to solve.
That true if I see now, in 6th test case, edge case is present and I might have caught that if I didn't check for sorted array before. :)
Can anyone tell me logic of Problem D
Note — the answer depends on the last element, then the next smaller element left to it...and so on till it reaches 0.
Shift the array such that 0 occurs at the 1st position,
now ans[i] = ans[previous_smaller_position[i]] + array[i]*(i-previous_smaller_position[i]);
I got pretest passed for "A. Constructive Problems". Since my solution wasn't Accepted, does this imply that it was wrong? Please guide.
It says Accepted to me
AC code
TLE code
How when I add this line get an AC?
someone explain me the proper logic behind B please
in every operation you can choose u and v as leave nodes and compress them. so in every operation you can decrease total no. of leaves by 2 so if no. of leaves is even it will take leaves / 2 operations. if no. of leaves is odd it will take leavs / 2 + 1 operations. ans = (leaves + 1) / 2.
Hello. There is an issue on the task C. During the contest, I had sent my code with c++20 and got TL. 237525118 But after the end of the cf I sent the same solution on c++17, and it was accepted.237531478
Pls do something with that.
That sometimes does happen man.
I think this has something to do with you using '+' operator to concatenate the strings, as it has higher time complexity. If you use push_back(), it will run smoothly. Submission
It appears that there is a discrepancy in the Problem C description. The task requires sorting a given string, but the sorting criteria are not explicitly defined. However, the jury's answer specifies that the output should be in non-decreasing order. This creates confusion because, for example, the input string
dccbbais already sorted in non-ascending order, but the jury's expected output is5. In contrast, the output could also be0since the string is already sorted. wdyt? intrusiv tibinyte2006 cadmiumkyThe statement was meant to clearly represent non-descending order. We are sorry for the confusion. We will analyze further for further action.
But, if we are to be pedantic, "sorted" then doesn't really mean anything, because if we so desperately need a criteria, we can choose any permutation to denote the actual order of the letters.
Thank you for your reply. I grasp your point. Thanks again.
Can anyone please help me understand why changing the CPP Version is resulting in different behaviour with the same code.
https://codeforces.me/submissions/ma_da_fa_ka
I got ACCEPTED, TLE, RTE with different version of cpp compilers.
Problem D: We can use
Binary liftingif the input array was not always a permutation of set $$$(0,1,2,..,n-1)$$$Submission: Link
could anyone please tell MEOW why is he/she/they/etc getting TLE for C?
Probably due to string concatenation being too slow
Why is my D getting TLE ? I tried to optimise the inner loop by jumping to the next smaller element each time using a stack, it should not be N^2 ?
237525237
You can try the following test case
This test case will force your step to be 1 for most of the positions.
Thanks. I overlooked this