Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 980 (Div.1, Div. 2), which will start on Oct/20/2024 12:05 (Moscow time). Note the unusual time of the round. Each division will have 6 problems and 2 hours to solve them. The round will be held according to the Codeforces rules and will be rated for both divisions.
The problems were authored and prepared by Mangooste, Tikhon228, adepteXiao, Artyom123, sevlll777, yunetive29, glebustim, Endagorion, isaf27 guided by Ormlis and Helen Andreeva.
The round is based on XXII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. Also thanks to the authors of the Olympiad whose problems were not included in the round : vaaven, TeaTime, pakhomovee, TheEvilBird, ch_egor.
We would like to thank specially:
- Artyom123 for his high-speed coordination.
- MikeMirzayanov for creating Codeforces and Polygon.
Great thanks to the testers: Kapt, SomethingNew, k1sara, Pekiban, automac, theRealChainman, marks39, cosenza, pengin_2000, Killever, perchuts, Endagorion, maomao90.
As well as the teams testing the main Olympiad: (RP-1, kostylevGO, PBBx0), (AgafonovArtem, blyat), (daubi, talant, alexxela12345), (tem_shett, crazyilian, sevlll777), (katyaporay, Igorbunov, Dart-Xeyter), Kirill22, (rama798, FlameDragon, egneeS), (MOHOXPOM, Goshix, shevnin_d), teraqqq, (Siberian, Um_nik), (kova1, Aleks5d), (makcvim, Silver_Fox), polosatic.
UPD1: Score distribution:
Div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
Div.1: 500 — 1000 — 1500 — 2250 — 2750 — 3000
UPD2: Due to the official competition source codes of other participants will not be available for two hours after the end of the round.
UPD3: Editorial
The trend of rounds based on other rounds.
Want to see tourist rating change.
Yeah, may the next destination of tourist is 5000+ rating
jiangly will be the next tourist.
As a tester I can guarantee that the contest consists of at least two problems.
As a tester I can confirm that there are problems.
As a tester,
the FitnessGram™ Pacer Test is a multistage aerobic capacity test that progressively gets more difficult as it continues. The 20 meter pacer test will begin in 30 seconds. Line up at the start. The running speed starts slowly, but gets faster each minute after you hear this signal. [beep] A single lap should be completed each time you hear this sound. [ding] Remember to run in a straight line, and run as long as possible. The second time you fail to complete a lap before the sound, your test is over. The test will begin on the word start. On your mark, get ready, start.
First time seeing so many RED author's excited to participant.
As a tester, as well as CEO of vulestamenkovic fan club, please join vulestamenkovic fan club.
I second that.
are there any requirements for joining?
As a tester I tested.
Linkedin version: I’d like to express my sincere gratitude for the opportunity to contribute to testing the recent Codeforces round. It was a great experience that allowed me to sharpen my problem-solving skills while supporting the quality of the contest. Being involved in such a meaningful project was both rewarding and insightful, and I truly appreciate the trust placed in me. I look forward to future opportunities to collaborate and contribute further. Thank you again!
The MX weekly contest coincides with the time of this contest, so I regret that I cannot participate in this contest.But I will Looking forward to your next contest!
I have registered for tomorrow's div1, what if I lose rating points in this one and become expert, will I be able to give both div1 and div2 simultaneously tomorrow?
Sadly you can confirm what'll happen now
Yeah I'm now registered for both contests, will try giving both at once.
Did you sacrifice points to find the answer to your question? I am genuinely interested in the answer too, please give an update.
I didn't wanna sacrifice points but my stupid brain was like use segtree, sets, 8 cases for simple D problem and here we are
Update it automatically unregistered me from div1 5 mins before the contest started.
watch me drop back to cm
Ok so turns out I am not going to fall back to cm
Clashes with CSP-J/S 2024 Simulation Test in luogu.
CF Div1 >>>>>>>> Luogu
I agree.
tourist is going to reach $$$4100+$$$ this time.
He did'nt participated
Shit :). I think he is busy with Meta Hacker Cup.
Last early (time) round like this also followed Meta Hacker Cup.
Are boarding schools common in your country? Are they strict?
Why can't anyone in 1900-2099 register for Div.2 this time ?
this is always the case for combined contests.
12 contests since newbie, yet havent faced rating decrease. I hope it never comes.
well done
That's impressive.. But is this your alt account?
Well few ppl i see are always crooked and cant tolerate others get what they couldnt, aint it ? Sad
lol why are you getting so triggered ? i just asked if u were practicing in other accounts or something cuz it seemed cool that you reached that so fast.. but i didnt know u were this much arrogant.. anyway happy coding and just an advice : try to be a little bit nice
lol
well, kid, prove !
ok
But that is only for C, for A, B and D, it doesn't look like cheating.
I use comments for Long codes for which i tend to forget variables. And for the rank, blame the ranking system, not me.
Also the code in which i gave comments didnt get accepted till end as my logic was wrong (which i got after the contest)
Also u arent someone to judge who is cheating or who is not ! mind your own business from next time !
First time seeing so many RED author's excited to participant.
what will be the score distribution for Div2?
RED Alert!
Please, show the score distribution.
Score distribution LOL
As a participant, the girl in Ormlis pfp is cute
nice score distribution
Wish to find a good problemset.
Hoping for the best CF round!
having a downfall since way too long now, hoping to atleast get back to 900 today :(
2 hours speedrun!
Hope orzdevinwang can reach Top5 in "Top rated" after the contest
Lost rating sadly... But the process of my performance in this contest is so dramatic that I want to share it.
That was Heartbreaking
udgm is a cheater, you can see his submissions.
he used chat GPT to solve problems and remove comments manually.
Please Ban him
How do you know this? Submissions aren't public and you haven't locked the one problem you solved.
im talking about previous submissions
I still don't see anything? Their previous submissions (at a quick glance) don't seem to show much GPT usage, plus they solved Maximum MEX first try (A problem which GPT o1 wasn't able to solve), yet didn't attempt E1 of that same contest, which o1 could solve
i hope cheaters like udgm get banned sooon.
I have never hated a question as much as B
It was a simple greedy problem!
Can you help in finding the flaw in my logic for problem B, as i am unable to find the case where it could fail 287013577, Thankyou
Solutions are locked. Instead, write your code here.
You are not considering the value of the previous elements, which had reduced the value of all the elements by their values.
now i get as we are doing operation on all the slots we have to remove their values as well, thanyou
Could you please explain how exactly you approached it? i had an idea of using each button once till it becomes zero and then not using that button again. but unfortunately it was wrong.
You might have forgotten to use
prev
if your approach is similar to mine.I attempt to take all the cans from the slots (by doing slot * e.first) until the slot with the minimum count allows it, as long as it is not zero. As soon as a slot becomes zero, I add the frequency of that slot to my answer, as these actions can be ignored for the slots that are now empty. I then reduce the number of slots accordingly (slots -= e.second) and repeat this process until k is no longer greater than zero.
why are we subtracting from prev?
I spend the whole contest on it (after I solved c and came back to it) and then the problem was just I used int instead of long long :)
means i was getting WA on pretest 9 cause i was using long long ?
no, because you are using int some where (that was the case for me)
Is fft required in 1C?
No: I have only KMP.
FFT in 1C?
EDIT: probably wrong, ignore
I don't think so, given that you only really need to solve the problem for $$$k=2$$$ and $$$k=4$$$ (for all "normal" cases, $$$k=1$$$ works and other values of $$$k$$$ fail).
What? How?
I just found a mistake in my proof of that. Oops.
The solution comes down to the following observation:
We need the digraph to be an SCC for this lemma to hold because of edges across SCCs don't have to be part of cycles.
With this observation, the problem is simple: we need to perform DFS over the 2 SCCs we are given. Now, if the 2 given SCCs dont form a cycle (all edges from one SCC are outgoing), then the answer is always YES, of course.
Otherwise, we need to find the "shift" of the second DFS tree wrt the first mod k. This is just finding if two arrays are cyclically equivalent, which can be done by hashing easily.
Very strong examples. I'm amazed.
Very strong examples. I'm amazed. Got -9 on 1C.
OMG Jiangly will become 3900+ after this, can't believe it! Congratulations to jeroenodb as well for becoming LGM!
is Div2-D graph??
Yes.
nah it is like a difference array except for minimums
can you explain the approach? I used dijkstra
Sure, so basically we can set up our answer as $$$pre_i - skipped_i$$$ where $$$pre_i$$$ is the prefix sum up to $$$i$$$ and $$$skipped_i$$$ is how many we have skipped to get to the $$$i^{th}$$$ index. So now we just have to minimize $$$skipped_i$$$.
To minimize $$$skipped_i$$$, it helps to see that the only possible answer for $$$i = 2$$$ is skipping $$$1$$$ (or $$$skipped_2 = \infty$$$ if we can't even reach $$$2$$$ from $$$1$$$). It follows that skipping $$$1$$$ lets us get to $$$[2, b_1]$$$ just by skipping $$$1$$$. So, in an "opening" difference array, we can place $$$a_i$$$ at index $$$2$$$ and in a "closing" difference array, we can place $$$a_i$$$ at $$$b_1 + 1$$$. This is assuming that $$$b_1 \ge 2$$$, because, otherwise, we don't have any skipping options for index $$$1$$$.
In each index $$$i$$$, we can get the minimum skipped by processing the difference arrays (adding any ones in the opening $$$i$$$, and removing any ones in the closing $$$i$$$ to a SortedList), and we can just take the minimum in the SortedList. That is the minimum skipped at index $$$i$$$. After processing an index, we must add $$$a_i + skipped_i$$$ to the opening difference array at $$$i + 1$$$ and $$$a_i + skipped_i$$$ to the closing difference array at $$$b_i + 1$$$. Of course, you have to make sure that $$$b_i \ge i + 1$$$. I hope that this is a clear explanation.
ohh i see, that makes sense. thank you
Nice method, but for example if $$$ j < i $$$ and when adding $$$a_i + skipped_i$$$ to the array $$$[i+1, b_i + 1]$$$, we could duplicate $$$skipped_j$$$, if we had already added it to $$$[j + 1, b_j + 1]$$$ , and both arrays intersect, isn't it?
Sorry but I'm not exactly sure what you're saying. The difference arrays make it so that each addition of $$$a_i + skipped_i$$$ is only two insertions.
I can't believe you became purple before me
you got so close fr
Yes, I am not talking about complexity, the problem is the value added to the difference array.
This example:
10 20 30 3 3 3
It can be proccessed like this :
$$$i = 1$$$ : $$$pref_1 = 10$$$, $$$skipped_1 = 0$$$
after we have add $$$a_1 + skipped_1 = 10$$$ to difference array $$$df = [0,10, 0 ,-10]$$$
$$$i = 2$$$ : $$$pref_2 = 30$$$, $$$skipped_2 = 10$$$
after we have add $$$a_2 + skipped_2 = 30$$$ to difference array $$$df = [0, 10, 30, -40]$$$
Or for $$$i = 2$$$ we can add only $$$a_2$$$ to the difference array, because skipped_2 which is $$$a_1$$$ had been added to actual difference array, during $$$i = 1$$$.
But by reading again, I think I misinterpreted. What are the insertion and the sorted list you talked about, and how you manage them with the difference array?
Ohhh these things aren't "real" difference arrays. They are kind of like difference arrays but on minimums.
For example, in your example $$$[10, 20, 30]$$$ $$$b = [3, 3, 3]$$$ the first step would be to process the element 10, and we see that, if we skip $$$10$$$, we can go to $$$2$$$ or $$$3$$$. So, to our opening difference array (which is a vec of vecs) at index $$$2$$$ (the vector at index $$$2$$$), we add $$$10$$$ and to our closing difference array at $$$b_1 + 1 = 4$$$, we add $$$10$$$ to the vector at index $$$4$$$.
Then, in our iteration, when we reach $$$2$$$, we add the opening element $$$10$$$ to a SortedList (so we can easily access the minimum element) and at index $$$4$$$ we remove the $$$10$$$ from the SortedList. It might be the case that the difference arrays can store multiple values.
Ah thanks, got it.
i was so damn close to solving B, im literally annoyed
Thank you for the round, the problem div2C really good even I can't solve it in contest time. Will upsolve it later.
e problem is hash problem?
Div. 2 A-D were really good problems, however E and F were too hard and made the contest a speedforces.
how did u do d?
dijkstra
can you please explain, how you use dijkstra?
I got it. We treat all the problems as a node. We add a edge from Node i to Node i-1 of Weight 0 (As we can always do that problem and come back to the previous problems.)
We also add edge from Node i to Node bi with the weight ai (As we can skip this problem and go to Node bi but with ai cost as we can't do this problem now).
Now we can use Dijkstra's to find the minimum cost to reach all problems from the First problem and find the answer
Can anyone help me how to solve Div2 C Concatenation of Arrays problem?
just sort the arrays ascendingly based on the summation of their two elements
Why does it work? Could you explain a little bit
i think you would want to keep elements with high value to right and in this case you can take (sum of array as whole element) then sort it
How you came up with that?
I don't now it just felt logical but I have no prove for that
Here's what I thought: If the sum of two numbers $$$(a,b)$$$ is greater than the sum of two numbers $$$(c,d)$$$, then it is necessary that at least one of the numbers from the first pair is greater than one of the numbers from the second pair. This way, the answer can never worsen. Rather, it can only improve. It kind of rested on ONE observation. Please share problems like these where the fate of the question lies on ONE observation.
I have another approach. Simply Sort the
vector<pair<int, int> pr(n)
based on,whichever pair has minimum value of
x = max(pr[i].first, pr[i].second)
comes first.if some pairs have equal values of
x
, then whichever pair between them has a minimum value ofy = min(pr[i].first, pr[i].second)
comes first.if some pairs also have equal
y
value, then whichever pair haspr[i].first < pr[i].second
comes first.hints on d? dp or greedy?
you may not believe me, but its neither :O
Well, my solution is DP.
can you please explain how? I though it was dp at first, but i solved with dijkstra in the end
Took the state to be dp[i] = min cost needed to reach index i.
So the final ans will be max( sum(a[j] {j = 0 to i}) — dp[i]) for all i in [0,n]
I mean sure, i do that as well, but how do you actually find the costs without using dijkstra?
Well for any node i you can go to all nodes between [i,b[i]] provided b[i]>i with a cost dp[i]+a[i].
Now store these values in a multiset. When u get to a node j, dp[j] = min(multiset).
Now update the multiset. (i.e) add dp[j]+b[j] if b[j]>j and remove all those dp values from multisets that lead you only till index j.
Works because the top sorted order is from 1 to n
i did dp + segment tree
let U[i] be the min cost skipped to get to i -> res would be $$$prefA[i] - U[i]$$$
from i -> you can go from 1 to B[i] for the cost of A[i] (you will be transported to B[i] where you can just slowly drop down)
updates can be done with a segment tree
then just calculate outwards from the start (U[i] <= U[i+1] is always true so it shouldnt wa)
Yes please explain both the approaches, I feel like crying now ,that I couldn't solve this problem.
If b[i] is less than i+1, you wont actually ever use that, so you can not care about that. So lets look at b[i] as directed edges from a[i] to b[i] whose costs are a[i]. We also have edges from each i to i-1, for all i>1. Those edges are obviously free. After this, you can just do dijkstra and you can find minimum cost to get to any i. Then the answer is just the maximum out of all a[i]-cost[i]
Could you explain the last line again, Why are we considering it ?
Should the answer be max{a[i] — cost[i]} or max{prefix_sum[i] — cost[i]} ?
yep prefix sum works
can u pls share ur code
Here is what I wrote based on his observation and submitted it. Got AC
Actually i think that i dont have to add free edges, because it is not optimal to go back (since the answer of j will be bigger than answer of i) (i<j)
Thats wrong because it can be optimal to go to the back edges, because some of them might be able to push us even more forward. Sample 2 shows that as well. And also the answer of j is not always bigger than i, for j>i.
I mean that instead of going back in the array, i can just maximize my answer with(pre[i] — skipped)
i dont understand what youre trying to say, but the back edges are necessary for dijkstra, maybe you could do it with another approach like that idk
I did dp.
Is the solution to Div 1C something along these lines?
For a graph where every cycle is divisible by $$$k$$$, you can number each node with a "remainder" by simple DFS from an arbitrary node.
Then the added edges must all connect a node with remainder $$$x$$$ in graph 1 to a node with remainder $$$(x + C) \mod k$$$ in graph 2 for some fixed $$$C$$$.
We can check this efficiently by:
[list 1] seperator [list 2] [list 2]
and seeing if there is match of size $$$|list 1|$$$.Also handle the obvious edge cases (outgoing / incoming list sizes not equal, all outgoing / incoming for a graph, etc) separately.
I can't see any obvious flaw in this logic but I'm getting WA on test case 2 and unfortunately writing a test generator for stress testing seems tougher than the problem itself.
you can also connect the 2nd graph back to the first graph (and it's not simply just (x+C)%k)
You need one extra step: checking if the new cycles formed by the edges you added alsohave lengths divisible by $$$k$$$. For all edges $$$(a_\mathrm{in}, a_\mathrm{out})$$$ from graph 1 to graph 2 and $$$(b_\mathrm{in}, b_\mathrm{out})$$$ from graph 2 to graph 1, you need to check if $$$(a_\mathrm{out} - a_\mathrm{in}) + (b_\mathrm{out} - b_\mathrm{in}) + 2 \equiv 0 \pmod k$$$.
In your solution, this corresponds to checking whether there are a pair of $$$C$$$'s for both "directions" of edges which have a difference of $$$- 2$$$ under modulo $$$k$$$.
Oops, yeah I just realized my solution implicitly considers the edges in the opposite direction to have length "-1" instead of "1".
Thanks for helping find the mistake.
Why the example of Div1 C is so weak.I don't have any time to generate a legal input in competition.
sorting the pairs based on the maximum element worked for Div2C. It was intuitive, can someone please explain why it works?
Wait what do you mean, i tried this in contest and it didn't work for me.
sorting based on max, but if the max elements are equal, sort on min elements.
if min and max both are equal, their position does not matter.
Suppose you put the array with the bigger maximum in front of the one with the smaller maximum, now you will create more inversions.
Yeah i thought the same, but it was not mathematical enough to convince me during the contest.
I got WA when I did it like that, then I sorted them based on the summations of the two elements no the maximum
I sorted based on minimum first and then maximum only to get WA on pretest 4. Then, I reversed the order and got AC. Still not able to understand how the order of checking min/max is affecting the algorithm.
I am so confused about C
Good contest. Great problems. Also how to solve D?
You can look at it as a directed graph. Every back edge is free, and every edge going forwards costs you the points that the starting point is worth, then its a simple dijkstra
really cool contest, this is the first time i actually used dijkstra in a contest
Actually 1B/2D can be solved without Dijkstra, but rather with DP optimized with BIT.
ahh i see, i have no idea how to use BIT sadly, so i couldnt really come up with that
Problem A and B were inspiring, I did them fast tho. C is kinda interesting for me (and I love graphs), just taken a little bit of time to solve. Other problems are too hard for me. I might gain rating.
In conclusion it's not undenying that this round is a STUPID TRASH ROUND.
what's the proof for d1A since i literally just blind guessed the sol
Consider pairs $$$(a,b)$$$ and $$$(x,y)$$$. If conditions $$$\min(a,b)\le \min(x,y)$$$ and $$$\max(a,b)\le \max(x,y)$$$ are both true, it's obvious that we should put the first pair before the second pair.
If such condition doesn't meet then their relative position doesn't matter.
let
inv(A, B)
be the number of inversions ifposition of pair A < position of pair B
if
A.first + A.second = B.first + B.second
theninv(A, B) = inv(B, A)
.if
A.first + A.second < B.first + B.second
theninv(A, B) <= inv(B, A)
, becausemax(B) > max(A)
ormin(B) > min(A)
holdsCan someone explain, how to solve task C?
Can anyone please explain where I am thinking wrong for problem b i try to take cans from each slot and as soon as i reach the minimum amount, i subtract all the slots having the min value from total number of available slots, Please help me in getting to know the flaw in my logic
Submission link: 287013577
jiangly orz
Div2 D is proof, I still don't know Dijkstra.
exactly. it looked like graphs but i wasn't sure on then how to use that knowledge
Solved it now using djikstra
I read the tutorial but quite not understand why we are allowed to visit each problem as many times as we want when using dijkstra to find minimum. Could you help me explain it
I understand that it is the contestants' responsibility to write correct code, but what is the purpose of 1C samples?
To test if some contestant is able to do stress testing.
The sample only needs to be able to clearly describe the meaning of the question.
To be honest, I think the constraints on the input could've been made more friendly so that the 2nd and the 3rd sample cases become unnecessary, by guaranteeing the number of in/outgoing vertices to be matched and that there is at least one in/outgoing vertex on both graphs.
Other than these trivial exceptions, the 1st sample was also way too simple that any wrong implemetation with several mistakes would still print
YES
, so the whole example barely tested anything with the core implementation.true
I am dumb
How to Solve Div 2 B?
I sorted the array and then used binary search to find the intervals where I could remove one can and how many cans I could remove on each interval
The strategy is to click all buttons, then in cycle click all that were nonempty in the previous step.
Thanks!
How to solve D?
did you try asking yourself ...
-is-this-fft-
LOL!!!!
If the sum of w is less than 200000, fft could solve the problem easily. However, the problem doesn't guarantee that. :(
BRO, my comment is a JOKE !!!!!!
LOOK AT HIS NAME... HIS NAME is -is-this-fft- . So I made a pun, may be it is FFT.
Nobody understands jokes these days.
why are you yelling
You are right my friend, Yelling is not FUN.
My small brain is fried, Cos no-one gets PUN.
Whats the solution for 2C?
create a vector to store each array as a pair of integers. Next, for each array, input its two elements and store them as pairs. Once all pairs are collected, sort them primarily by the first element and secondarily by the second element when the first elements are equal. Finally, concatenate the sorted pairs into a single array, ensuring the relative order minimizes inversions by keeping smaller elements before larger ones as much as possible...
thanks, I didnt think it would be so “simple”
Any hint on D1/D (D2/F)?
I came up with some observations that a game can be added only if (wi * pi/(1-pi)) is greater than the summation of previous added weights, but couldn't use it in dp or greedy
1/(1-pi)<=100, so the constraint from the statement implies that the sum of previous added weights is <=2e5. You can also use that formula to conclude that you should take at most 1/(1-pi) weights of a given pi. In total now you have 100+100/2+100/3+...=approximately 500 things you have to consider, and the sum of weights is <=2e5, so dp[i]=max probability with sum i works fast enough.
I used dijkstra for div2 D but I got TLE at TC24. Can someone please explain why my solution is this slow?
Submission link
UPD2: Due to the official competition source codes of other participants will not be available for two hours after the end of the round.
u can check that blog
Thanks. I will check it.
Are you maybe using max-heap instead of min? Thats how i got a tle at first
I used min-heap. You can check my code below.
maybe emplace is slow? i used push
oh and also why do you have >= in "(i > 0 && mn[i — 1] >= w)", should it not be just >? i think this is redundant and slows down your solution.
Oh, I see. Thanks for the help.
I updated and resubmitted and it passed with 265 ms. I never knew such seemingly minor changes can affect the time this much.
anytime a node was reached and the weight before it was equal, it would essentialy make an entire line back to the start, so with a good enough test case that was probably n^2 sadly. but atleast your idea was correct, just a minor implementation issue
Hello, could you let me know why you used vector mn = ap; I don't understand why If I use vector mn(n, INT_MAX); there, I get WA at tc 15
Updated: I got it, I should use LONG LONG MAX
In your solution to find the minimum to reach the problem i, I understand that we are allowed to visit each problem as many times as we want, right? Could you explain why we are allowed to do that?
Could you explain how to use dijkstra here? Thanks.
updated: Got the idea, each index i can either submited(go to i-1) or skip(go to b[i])
use heap to update value in correct order.
How to div2 E, I think it similar to https://atcoder.jp/contests/arc144/tasks/arc144_e, but i have no idea
Consider the 2 graphs, for each node u can find its relative position%k, as its relative positions to each other mod k is guaranteed due to the the property of cycles length is divisible by k. We keep track of count of each position mod k separated by graph and also by input and output. What we want is for all the output of first graph to be 1 before the input of second graph. We can do this by checking equality for all rotations of k for the second graph and seeing if the 2 graphs sync together. Equality can be checked using rolling hash.
I have given the contest using my own personal two codeforce account so the submission I have made on both the accounts is same , so will I get penalty for the plagiarism over this?
Obviously yes
You will be banned by Mike.
Can anyone tell where I'm missing? I am trying this approach to solve B but getting WA on 2
Nice problemset and Problem D was beatiful
jiangly %%%
what's wrong with my idea of Div2 B?
I thought that — In the worst case, we always press the button with the smallest cans. So, I took the smallest can and removed all elements from it and the elements to right of it.
your intuition is correct but see you press every button once so you will get (min_ele*n) cans evrytime you press button after then you will get no can so you learnt that that slot with min cans became empty and so on...
Yes, that's what I did in the implementation. What is the flaw here?
Pressing a button with minimal cost may not necessarily result in greater profits, which is clearly not a problem of greed.
You don’t have to necessarily reduce a number to zero. You could just pass the other moves left to higher values. Think of it as pressing the buttons in a cyclic manner
So why are we allowed to discuss solutions about the mirror contest on codeforces if the official contest isn't finished?
Hello 2024
The Div.2 contest is numbered 2024......
Haha,I also find that.
congrats to jiangly
less than 100 points to T now
He will become 'J' and not 'T'.
Maybe we would see a Tourist jiangly soon if he keep taking top 1.
…and tourist does not participate as well :)
Edit: meant to say that if both of them compete, we may only have one Tourist ranked
This contest looks unusual to me only?
Here, people starting with rank around 950, till 5k have only solved ABC (some outliers with ABD), but then the ranking comes down to just who did it faster.
It seemed that C was just a hit and try to sort by max then submit, then sort by min and submit or sort by sum and submit, etc
I don't know if this is correct, so I use several different ways to sort, and then calculate the inversion numbers, finally choose the least one.
This has to do with the round being a combined Div1+2 round, so the purple contestants are competing in Div1 rather than Div2 when it's a standalone Div2 round. Almost everyone (~1k contestants) solved AB in Div1 (equivalently CD in Div2), and if you count these in we have ~6k solving up to Div2C and ~2k solving up to Div2D, which is a more normal ratio (around 3:1) instead of the apparent 5:1 ratio.
That's some nice statistics. But my focus was more on that 5k people solved atleast C in Div-2 which seemed unusual to me and hints that C was quite easier than it should have been.
I have no proof for my C, just do guessforces...
I can't see your source, but most solutions should be based on this observation: In-pair order doesn't matter, so we can put them first small and then big.
You can observe that you pair a to come before pair b only if (a1 < b1 and a2 <= b2), or (a1 <= b1 and a2 < b2).
You can also observe that for pairs between a and b, they would always minimize or maintain inversions due to the swapping of a and b and for those outside a and b, nothing changes.
Although not that useful for getting the optimal complexity, you can also see the problem as a topological sort problem, as the data permits a partial ordering and you can come up with different systems that give you the optimal solution.
topo sort? Are u sure? It's just greedy.
Yeah, I meant you can make your greedy based on the observation it's a topological sort problem. You can come up with different strategies to satisfy the sorting. Either you order by summing up the pair members, or you do it by comparing first elements then second elements, only important thing is that your strategy allows a partial ordering.
In my totally unbiased opinion, this was a good contest. Thanks for the problems!
Agreed. Problems felt refreshing with tough but not impossible ideas. Haven't felt like this after the contest in a while. It even makes me want to upsolve the contest :)
Please uphack my $$$O(k^2)$$$ solution for D1C
287064329
Hack
When will the editorial be out?
I solved the first question but got no rating, after by code being submitted successfully. Also in the previous contest yesterday i solved the first question successfully in first attempt but got rating of -10 , can anyone explain this..
Your rating directly relates with your rank, and not the number of problems you solve. Today, your rank was exactly what is expected at your rating, hence no rating change. Yesterday, your rank corresponded to -10. Read more: CF Rating System
Six months later, I'm still 1400.I want to become blue.
that's why!
you should solve more problems of these (1600 < rating points )
How to see the problem ratings? Is it mod?
Install CF Analytics on your browser
Thanks a lot! Wish you a good week!
Thank you! Wishing you a great week ahead too :)
A grey is showing a Cyan about what he lacks for touching Blue xD things you only get to see in CF!
How can I have such an attractive chart?
My bad , just read your comment again !
Install CF Analytics on your browser to see this
Oh, sorry about that Thank you very much anyway
It has been almost 4 hours since the round ended. When will others' submissions be available?
6 now
sir Ormlis, we cannot access the details of our submissions and others' codes currently, please fix it
Sorry, I thought it was available a long time ago. I pinged the coordinator.
So what's C+K+S in div1C? In Russian in could be interpreted as parity (Ч) + quantity (К) + sum (S), but it's different in English. And the solution seems to have nothing to di with parity... So what's it?
Ormlis when can we view solutions of others? :'(
I solved div2D using DP + Segment Trees. The code is short and simple. Here is my submission if anyone is interested : 287094337
Can anyone tell me why my Div. 2 C doesn't work? The idea: Pair (a,b) comes before (c,d) if at least two of these inequalities hold: a <= c, a <= d, b <= c, b <= d. Else, pair (c,d) comes before (a,b)
I made a comparator with this logic and sorted the pairs. Doesn't work
Even I had a similar approach.
In the comparator, I took 2 scenarios, one when Ai is on the left of Aj and then calculated the inversions caused by it, and another scenario when Aj is on the left of Ai. Then whichever is better in the 2 scenarios, I just took that.
But this approach also gives WA on test 3.
Can someone tell why this does'nt work?
There is an edge case when number of inversions in both orders is equal. In such a case, putting the pair with the largest number on the right gets AC. I don't know why though
i also used comparator ,my comparator funciton that gave error on test 2: _
bool comp(pair<int, int> &a, pair<int, int> &b)
{
int sa = 0 + (a.first > b.first) + (a.first > b.second) + (a.second > b.first) + (a.second > b.second);
int sb = 0 + (b.first > a.first) + (b.first > a.second) + (b.second > a.first) + (b.second > a.second);
if (sa > sb)
{
return 0;
}
} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
after adding a small if condition gave an accepted, dont know why ...
bool comp(pair<int, int> &a, pair<int, int> &b)
{
int sa = 0 + (a.first > b.first) + (a.first > b.second) + (a.second > b.first) + (a.second > b.second);
int sb = 0 + (b.first > a.first) + (b.first > a.second) + (b.second > a.first) + (b.second > a.second);
if (sa > sb)
{
return 0;
}
if (sa == sb) // extra if condition
{
if (max(a.first, a.second) > max(b.first, b.second))
{
return 0;
}
else
{
return 1;
}
}
return 1;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~ can someone suggest a test case for better understanding.
ig you have missed the a>=d check
my comp function is :
bool maxm(pair<int,int>&a,pair<int,int>&b){ int amax=max(a.first,a.second); int bmax=max(b.first,b.second); int amin=min(a.first,a.second); int bmin=min(b.first,b.second);
}
it works
The main problem of it, is an absence of transitivity (look at the third clause here: https://mirror.codeforces.com/blog/entry/72525). This means that if your comparator tells that
a < b
andb < c
it MUST tell thata < c
.But with that instruction this is not allways true. For example:
(6, 2) < (4, 3)
(2 inequalities are true),(4, 3) < (5, 1)
(2 inequalities are true), but(5, 1) < (6, 2)
(3 inequalities are true).Without taking into account this condition (transitivity) the comparator isn't strict enough for c++, so the code can get any verdict, like RE or WA.
But this is not the main problem. Even though it's correct, we (not a program) can not choose wich option is better.
Thanks! This knowledge is life-changing
In div2C probkem i wrote a program that runs in O(nlog(n) but stille got TLE. Am i wrong in my calculations or is it because python is too slow?287015824
Still Not Able to see others Answer
Ahhh...please let me see the submissions and make peace with Div2/B.. :(
bro :(
Tried a lot, can't handle any more pain :)
._.
To solve the problem B, first sort the slots by the number of cans to prioritize slots with fewer cans, minimizing button presses. Then, start pressing buttons for each slot, collecting cans one by one. For each slot, calculate the maximum number of cans that can be collected from that slot and reduce the target number of cans
k
accordingly. Continue pressing buttons until you’ve collected at leastk
cans, keeping track of the total number of presses required. Stop once the required cans are collected and return the total number of button presses.thanks bro
Officially 10 hours without seeing others' solutions (well 8h after end of contest)
Can anyone help me to solve problems C. concatenation of arrays?
How should I approach?
Sort the arrays by their sum
Got it Thank you
Create a vector to store each array as a pair of integers. Next, for each array, input its two elements and store them as pairs. Once all pairs are collected, sort them primarily by the first element and secondarily by the second element when the first elements are equal. Finally, concatenate the sorted pairs into a single array, ensuring the relative order minimizes inversions by keeping smaller elements before larger ones as much as possible..
Brother, the code you've written and the logic that you say are different. The code is correct, but the logic that you've written in your comment is not
my bad this one is my updated code!!.. actually i just sorted the pairs based on the sum of their two elements, which effectively minimizes inversions by placing pairs with smaller sums first. This approach aligns with the goal of keeping smaller elements before larger ones, even though it doesn't use standard lexicographical order. so, the logic meets the problem's requirements and gives the correct output....
You can sort it by the sum of 1st and 2nd pair.
yes
deleted
Seems like I was the only person in the top 800 to make the amusing move of "2023B - Skipping" problem B...
Why did this get removed from the home page (at the time of writing this the topmost thing on the homepage is round 979)?
Just out of curiosity, how did you generate graphs required for Div1 C?
Can someone explain why this solution is giving wrong ans ?
My logics
I will choose the cans in a cyclic order. So I calculated the number of cycles that I will take by doing ceilfunction(k/n) so which ever number is shorter than ceilfunction(n/k) only that will contribute to the extra button presses other than the k button presses. So what I did was I counted the number of numbers less than ceilfunction(k/n)(let's call it x) and then my answer was k+x.
link to my submission https://mirror.codeforces.com/contest/2024/submission/286933505
Thanks in advance for helping :)
As a tester, I managed to scam D1D using a solution that possibly has exponential runtime. However, the authors did not kill it, and it still passes in 1671ms 287035100. Feel free to hack my solution :)
I think "ragam_ganesh_babu" vp this contest with gpt and i am surprised that it finish div1 a,b and d,e!
E is just copied from _l_l_.
I doubt it's GPT for the other problems either. Maybe some easier ones are. More likely ragam_ganesh_babu is just one of these people who like to "win" VCs by copying others' code in the first 10 minutes.
However, gpt solve Div1 B quickly and i solve it in almost 20 minutes:(
Edit: Perhaps he issued instructions for GPT to rewrite a certain code, but I don't think it's necessary to continue discussing this clown
287139892 Can someone pls tell why does this TLE ? I just iterated on the vector containing unique elements from the array inside the predicate function...
Can someone please help me understand the issue here:
Problem: 2024C - Concatenation of Arrays
Issue: Runtime Error on Test 4 with exit code: -1073741819 (STATUS_ACCESS_VIOLATION)
Submission:
my_comparators
for the sort function).compp
for the sort function).Attaching code incase submission isn't accessible:
Thanks for the help!
The compare function you use to sort the array should not be swappable. or to say cmp(a,b) and cmp(b,a) should not be TRUE at the same time
Thanks a lot! That helped!
Is there any problems similar to Div.2 C? I want to get some practice on constructive algorithm problems using greedy and sorting like this. Really appreciate it if anyone could give me some advice.
Can we add the following test case for Div2C & rejudge all the solutions?
Mangooste
10 4 4 10 and 4 10 10 4 have 2 inversion... both ways will correct why do you want to rejudge?
Ahh yes!!, I just zoned out there, maybe I was trying to over engineer. Never mind
Hey I am being accused of leaking answer or coping internet from the internet, which is absolutely wrong. I haven't indulged myself in any sort of cheating ever and it's just an mistake please look into the matter and do the needful. If you need any proof I can present everything
Your solution 287001298 for the problem 2024C significantly coincides with solutions pvr04/286984233, redcapp_caos/287001298
That's so silly, I clearly wrote the code completely on my own. I don't even know who the other user is. While there is a lot of cheating going on it is embarrassing that people like me who are giving contest fairly are put under this test. I don't know where to comment and what to comment.
Could have been the use of custom sort for this message.
I hope you guys understand my concern and act accordingly.
same bro same.. please upvote my comment too. they are just making these site worse, by not really catching the real culprits and making us look like that
MikeMirzayanov , Ormlis , Artyom123 , Mangooste , Tikhon228 , adepteXiao , Artyom123 , sevlll777 , yunetive29 , glebustim , Endagorion ,isaf27
I recently received a message regarding a similarity between my solution (ID: 286971111) and another user’s solution (Mradul2004, ID: 286933028) for problem 2024C. I want to clarify that I did not engage in any form of cheating, nor do I know the other person.Here’s my code:
Given the simplicity of the code and logic for this problem, I believe there’s a high chance of similar approaches being used by different participants.
I independently developed this solution and did not share it with anyone. Please let me know if there is anything further I can provide to clarify this matter(I have not used any publicly available code).
Thank you,