Привет, Codeforces! Мы рады пригласить вас принять участие в Codeforces Round 980 (Div.1, Div.2), который начнется 20.10.2024 12:05 (Московское время). Обратите внимание на необычное время начала раунда. В каждом дивизионе будет 6 задач, на решение которых отведено 2 часа. Раунд будет проведен в соответствии с правилами Codeforces и будет рейтинговым для обоих дивизионов.
Задачи были составлены и подготовлены Mangooste, Tikhon228, adepteXiao, Artyom123, sevlll777, yunetive29, glebustim, Endagorion, isaf27 под руководством Ormlis и Андреевой Елены Владимировны.
Раунд основан на XXII Московской командной олимпиаде для школьников, которая является отборочным этапом для Всероссийской командной олимпиады. Также спасибо авторам задач олимпиады, которые не вошли в раунд : vaaven, TeaTime, pakhomovee, TheEvilBird, ch_egor.
Мы особенно благодарим:
- Artyom123 за его высокоскоростную координацию.
- MikeMirzayanov за создание Codeforces и Polygon.
Огромная благодарность тестировщикам: Kapt, SomethingNew, k1sara, Pekiban, automac, theRealChainman, marks39, cosenza, pengin_2000, SmartCoder, perchuts, Endagorion, maomao90.
А также командам, тестировавшим основную олимпиаду: (RP-1, kostylevGO, PBBx0), (AgafonovArtem, turist), (allvik66, mutant, alexxela12345), (tem_shett, crazyilian, sevlll777), (katyaporay, Igorbunov, Dart-Xeyter), Kirill22, (rama798, FlameDragon, egneeS), (alexsushin, Goshix, shevnin_d), teraqqq, (Siberian, Um_nik), (kova1, Aleks5d), (makcvim, Silver_Fox), polosatic.
UPD1: Разбалловка:
Div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
Div.1: 500 — 1000 — 1500 — 2250 — 2750 — 3000
UPD2: Из-за проведения официального соревнования исходные коды других участников будут недоступны еще два часа после окончания раунда.
UPD3: Editorial
Обратите внимание, что раунд по времени пересекается с очным и онлайн-финалом фестиваля RuCode — https://rucode.net/final-2024/ — который пройдет с 10:00 до 15:00 мск.
Есть ли возможность подвинуть CF раунд, чтобы участники могли принять участие в обоих турнирах?
Раунд проходит одновременно с олимпиадой, сложно гарантировать что участники не будут распространяться о задачах после олимпиады. Поэтому возможности провести в другое время нет(
The trend of rounds based on other rounds.
Want to see tourist rating change.
Yeah, may the next destination of tourist is 5000+ rating
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
Last early (time) round like this also followed Meta Hacker Cup.
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
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 !
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.
having a downfall since way too long now, hoping to atleast get back to 900 today :(
2 hours speedrun!
Hope zhoukangyang 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.
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 have never hated a question as much as B
It was a simple greedy problem!
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 ?
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 \lt 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.
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?
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?
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.
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
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.
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 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 Bif
A.first + A.second = B.first + B.secondtheninv(A, B) = inv(B, A).if
A.first + A.second < B.first + B.secondtheninv(A, B) <= inv(B, A), becausemax(B) > max(A)ormin(B) > min(A)holdsCan someone explain, how to solve task C?
jiangly orz
Div2 D is proof, I still don't know Dijkstra.
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
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...
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
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.
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.
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.
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.
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.
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 :)
How can I have such an attractive chart?
My bad , just read your comment again !
Install CF Analytics on your browser to see this
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?
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);
if(amax>bmax)return false; else if(amax==bmax) { if(amin>bmin)return false; else return true; }else return true;}
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 < bandb < cit 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
kaccordingly. Continue pressing buttons until you’ve collected at leastkcans, keeping track of the total number of presses required. Stop once the required cans are collected and return the total number of button presses.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
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
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?
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_comparatorsfor the sort function).comppfor 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
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.
А где благодарность MikeMirzayanov за создание Codeforces и Polygon?
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?
Уважаемый Михаил Мирзаянов, мое решение Napoleon/286906288(https://mirror.codeforces.com/contest/2024/submission/286906288) совпало с решением soumil.kumar/287015730(https://mirror.codeforces.com/contest/2024/submission/287015730). Полагаю, что это произошло из-за того, что soumil.kumar использует мои шаблоны, которыми я пользуюсь на абсолютно всех онлайн соревнованиях, вероятно данный пользователь использует мой код, который я писал на предыдущих соревнованиях. Я никогда не пользовался онлайн хранилищами или ideone.com, также я никогда не имел связей и друзей в Индии, поэтому мне нету смысла помогать ему в решении задачи. Для меня, как школьника codeforces служит прекрасной платформой для тренировок и мне не зачем делиться решениями задачи с soumil.kumar, которого я не знаю и никогда не видел.
Надеюсь, Вы поможете мне в данной ситуации, большое спасибо!
P.S. Решение задачи очень маленькое, ввод-вывод очень стандартные, сортировка тоже, вероятно пользователь изучал мои старые коды, я считаю, что совпадение в такой короткой задаче вполне могло произойти, ведь в раунде участвовало много человек.
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,
Dear Codeforces Team and @Ormlis,
I am reaching out regarding my submission (link: https://mirror.codeforces.com/contest/2024/submission/286986376), which was flagged for plagiarism due to similarities with another submission (link: https://mirror.codeforces.com/contest/2024/submission/286984393). I would like to clarify the following points to request a re-evaluation:
The logic and code structure for this problem are simple and naturally lead to similar solutions across different submissions. When a problem is straightforward, it’s common for solutions to resemble each other.
My submission includes a custom comparator function to sort a vector of pairs by their sum. This function was sourced from a publicly available answer on Stack Overflow (link: https://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair), and it’s widely used by many programmers. Leveraging such standard resources is a common practice and does not constitute plagiarism, as the code is accessible to everyone.
The similarity in variable names is coincidental and does not imply any copying or unfair means. Common names often align across submissions when variables are named descriptively.
I assure you that my submission is entirely my work, and I adhered strictly to the contest’s rules. I did not engage in any dishonest practices.
Given these points, I respectfully request a careful re-evaluation of my submission. The similarities noted are due to the straightforward nature of the problem and the use of standard, publicly available resources.
Thank you for your consideration.
.
https://mirror.codeforces.com/submissions/deepiit.gupta This is my submission link Sorry for the previous one
Dear Codeforces Team,
I am reaching out regarding my submission (link: https://mirror.codeforces.com/contest/2024/submission/287008334), which was flagged for plagiarism due to similarities with another submission (link: https://mirror.codeforces.com/contest/2024/submission/286991479). I would like to clarify the following points to request a re-evaluation:
The logic and code structure for this problem are simple and naturally lead to similar solutions across different submissions. When a problem is straightforward, it’s common for solutions to resemble each other.
My submission includes a custom comparator function to sort a vector of pairs by their sum. This function was sourced from a publicly available answer on Stack Overflow (link: https://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair), and it’s widely used by many programmers. Leveraging such standard resources is a common practice and does not constitute plagiarism, as the code is accessible to everyone.
The similarity in variable names is coincidental and does not imply any copying or unfair means. Common names often align across submissions when variables are named descriptively.
I assure you that my submission is entirely my work, and I adhered strictly to the contest’s rules. I did not engage in any dishonest practices.
Given these points, I respectfully request a careful re-evaluation of my submission. The similarities noted are due to the straightforward nature of the problem and the use of standard, publicly available resources.
Thank you for your consideration.