Div2A
Div2B
Div1A
Div1B
Div1C
Div1D
Div1E
Div1F
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
D1B
Unable to parse markup [type=CF_MATHJAX]
No way I set an alarm for 4:30 AM for this......
Can't imagine how many downvotes it will get!!!
I am a newbie, could you tell me why this tutorial get so much downvotes
Questions in this problemset were so much hard to understand, so many people could not answer because they couldn't understand what is this problem actually wants
thank you for your replying!
why did the contest begin early
B was a reading comprehension question :) for me
For the first time in life i felt like my english was weak. The last time i felt this was a decade ago lol.
yes, so am i. can not understand B. can you interpret B?
Yea sure man. (apologies, i dont know how to use the markdown thingy for symbol text)
Think of it this way. there is a number line from 0 to 1e9. an array is given, of n numbers. a0, a1, a2... an. these numbers lie on the number line. anywhere. these are the houses.
You are also given a number k. now thing is, at a point of time when you buy any house, at most "k" amount of houses could be in a state "already sold" so you cant buy them. So what can you buy? the n-k houses. The function will be Σ|x — y|, which is basically the distance between the ith house (you want to buy) and all the other houses.
Which basically boils down to this:
For the ith house, what is the minimum cost you can get, after removing at most k houses.
Suppose you have houses at locations: [1, 2, 3, 10], and k = 1. So you are allowed to remove at most 1 house to minimize your total distance.
Now, for example, if you pick house 2:
Without removing anything: cost ==> |2-1| + |2-2| + |2-3| + |2-10| = 1 + 0 + 1 + 8 = 10
You can remove at most 1 house. Obviously, the farthest house (10) is causing most of the trouble.
Remove house 10 , which leads to ==> new cost = |2-1| + |2-2| + |2-3| = 1 + 0 + 1 = 2
So after removal, cost becomes 2.
Now for different houses, you will get different minimized costs after removing at most 1 house. The goal is to find which house/houses can achieve the minimum possible cost (after removal) and count them.
The editorial talks about median :- why??
coz u wanna minimize Σ|x — y|, so u should choose a median of the points (after removing the worst k).
Kindly correct if i am wrong ( i think i might be, took me a lot of time to think this out -_-)
Bro, good explanation. If the problem statement had been around this, there would have been more submissions.
Nice man! I believe that my teameat can understand this question abusolutely after reading your explanation ^_^
can you explain 4th part of the sample test case?
6 2
5 1 9 10 13 2
so this means we hvae n = 6 (6 bars or houses) k = 2 (up to 2 bars can "close", i.e., you can remove up to 2 bars)
SO now u need to see which segment to keep. u can remove 1 from left and 13 from right, OR you can remove 1 and 2 from left, or 10 and 13 from right, and so on and so forth.
Thanks
Broo...this is too good. Thanks
Problem Statement is confusing but soln below is too good to understand .
If you read the provided test cases it becomes clear, no? Don't blame problem creators for you not reading all information given in the problem.
I wrote
`B was a reading comprehension question :) for me
For the first time in life i felt like my english was weak. The last time i felt this was a decade ago lol.`
Where in this did i blame/bash/criticize the author? I am talking about my own shortcomings. I felt like my english is weak. Where are you reading that I am blaming the problem creators? I dont understand sorry.
sure. The problem is ambiguous for me as a native English speaker, but I was able to understand it completely after reading the system tests.
So from next contest , read only test cases and solve it
same here :(
Completely true, I too wasted a lot of time and got discouraged from this Question -- the explaination below is much better than what the q had.
Sadge ( I dont blame the organizers though -- its not sure that I would ve solved the q with the better explaination either ^^)
so where is the codes?
thanks for contest, don't mind downvoters, they didn't read system test cases provided
The second problem was not clear at all, it was very poorly written. Having to bend the statement to fit the test cases makes it a very bad problem
As contest as editorial
please don't downvote folks.. that is so sad to see.
Everyone is very rude, it's not easy to create a contest and this is how you treat someone who provides you creative problems for free. 1B was nice.
no I understand they are frustrated but mass downvoting is not cool.
The system tests for D1B don't contain the case where there is a non-degenerate cycle and a loop in the same component. I feel like this is a pretty major edge case for anyone who detected loops and cycles separately. Uphacked solution: 317312034
Codeforces should be now be termed as aptitude forces .......
problem B is harder than c
is it possible to add sample solution code as well ?.. today I feel lazy to upsolve but maybe I will try tomorrow.
C was really great, but B was too hard to understand for me...
This is the first time I compete in Div1. Now I know the difficulty.I solved 2 problems.
Regular Div1 seems not like this, although I think the problems are interesting.
People that solved div1C, how did you come up with this representation that is proposed in editorial? Did you see it elsewhere? Honestly it feels like a magic to me.
Its an extremely common trick in math contest geometry problems involving reflection.
How do you use CRT on the two congruences? I thought CRT only applies when the moduli are coprime. Is there some extension to CRT that applies in this case?
https://oi.wiki/math/number-theory/crt/#%E6%89%A9%E5%B1%95%E6%A8%A1%E6%95%B0%E4%B8%8D%E4%BA%92%E8%B4%A8%E7%9A%84%E6%83%85%E5%86%B5 this is a website in chinese about extended CRT,you can translate it.
Seems this can be solved by extended Chinese Remainder Theorem(exCRT)
(vx)t+x≡0(modn) (vy)t+y≡0(modn) I merged these 2 functions to 1 function: (vx)t+x — ((vy)t+y) ≡ 0 (modn) Then this can be solved by Extended Euclidean Algorithm(exGCD)
D1B is pretty much the same as this problem
what bout D2C ?
Thank you for this info.
How to come up with Div1B ?
Drawing the graph on paper and it kinda makes sense but i'm not sure how to prove that if it has as many edges as vertices there is exactly one loop, that if it has less it is a tree and that if it's a tree there's #vertices possibilities.
Also i'm not sure what intuition leads you to studying that graph ? (I was trying to count perfect matchings in the bipartite graph between odd and even p's)
Does these kind of graph to solve interleaving constraints have a name ? Is somewhat of a general technique ?
You were on the right track with the number of perfect matchings in bipartite graph. The key detail here is that all nodes have degree <= 2, which lets us get the count too. The solution to this problem which I've seen before does the same thing as the editorial.
If a node from the left side of bipartite graph connects to u and v at the right side, you create a new graph where there is an edge between u and v. Do this modification for all pairs of edges in the original graph (if there is only one edge, in other words only u, add the self loop u-u instead).
The problem of perfect matchings in bipartite graph has now been converted to giving direction to the edges in the new graph. Now you can figure out the rest yourself.
I learnt this idea from here: https://www.youtube.com/watch?v=PdCnYQqadlQ (Around 15 mins is where Radoslav starts explaining that idea)
Thanks for your Div2.D, it made me almost smash my keyboard during the game.
From the editorial of div1D:
Because at n<1e5, anything works.
Also, if the code runs faster on modern systems, then why make restrictions for older computers on which this code will not run?
in next contest try to write proper statement,, don't make us to guess the problem instead of solution again...
Wait, is $$$10^9$$$ supposed to pass nowadays?
Anyway I guess you don't want to make $$$O(n^2/w)$$$ pass. In that case, maybe $$$n \leq 5 \cdot 10^5$$$ (or a slightly higher time limit) is fine?
What the hell do you exactly mean by 'anything'?
In addition, what is your reply to the first question?
Translation error. For the analysis, it was easier for me to introduce the concepts of linear algebra. And I tried to calm people who are not familiar with this kind of reasoning.
So that people would be more motivated to read the analysis and learn why Gauss works in this problem.
Using Gauss in this kind of problem, instead of searching for an invariant, seemed like an interesting idea to me. This task has a clear problem that you can just write a solution without proof, but it seems that a person who is not able to provide the proof above will not do this.
I think the XOR Basis algorithm (without linear algebra explanations) is already much more well-known (and easier to get familiar with) than a linear algebra concept. And I don't think the problem is hard enough for the position in either perspective.
Could you explain XOR Basis without referring to the concepts of linear algebra?
There is a blog titled that https://mirror.codeforces.com/blog/entry/100066 by Everule
Let me be more specific: to someone who has studied linear algebra systematically, XOR Basis isn't an issue (It should just be trivial). To someone who hasn't, it makes no difference if you just make a name change in the terms and be less professional in introducing this algorithm, which does make the concept more acceptable.
I know the essence of the algorithm is just linear algebra (and knowing it makes mastering the algorithm fast), but it does not mean linear algebra is a preknowledge here. The point is, the name of a term in linear algebra does not help reduce the problem itself (and even makes the editorial writer more tiring since he needs to type large LaTeX formulas). On the assumption that the editorial is written for those who skipped linear algebra classes / hasn't ever com across linear algebra, I think the current tutorial is a failure: like the solution steps are actually A to B to C all the way to Z, he explained X to Y to Z carefully, but what about those who only get to know A?
I should have realized that there are many differences in Chinese and Western education, especially in fields like advanced Maths. Thanks to linear algebra being included in many important exams, the Internet is full of low-quality, incomprehensible tutorials of linear algebra in Chinese. On the other hand, I've seen some nice blogs/articles on XOR Basis without referring to any of linear algebra, such as the thesis of Chen Xinyang, in the Collection of Theses of the 2025 Chinese National Trining Team.
I think there are better ways to motivate the fact that you divide n by the largest power of two possible than "I do it, here is a matrix, look I can swap rows and do transvections thus I can use gaussian...". Typically, you could have explained things with a geometrical point of view instead (so talking about bit vectors, explaining how you end up with $$$\frac{n}{2^k}$$$ vectors, and how the problem reduces to comparing the span of two set of vectors (which you can do with xor basis, or gaussian elimination)).
I'm still confused about the statement of Div2B.
Let's say I have a test case like this:
1
4 3
1 10 100 1000
Can anyone please explain why the answer should be 1000 and not 4 (according to the statement)?
you can remove 10 and 100 then you have 1 and 1000 and from 1 to 1000 will be minimal f(x)
Got it. Thanks.
so in this case, you may delete up to 3 bars, and any house that can be a median after up to 3 deletions is valid for a house location.
deleting 10 and 100, you have 1 and 1000 left, and any house between them achieves the minimum score of absolute distance to bars = 999. Therefore all of these houses are valid in this case, so you have 1000 possible houses.
i thought the problems were pretty cool. div2B took me extremely long to understand but thats probably an issue on my end lol.
For D1B, I don't understand why the answer is $$$2$$$ for non-degenerate cycle case. Such a component will have equal number of edges and vertices, where choosing all the vertices is the only valid assignment.
You can view the task as assigning a direction to each edge such that every vertex has in-degree at most 1. For the case of a non-degenerate cycle, flipping all of the edges in the cycle will give you another valid assignment (in the original problem, even if the set of selected cells is the same, there are two possible ways to assign them to $$$p_2,p_4,...,p_{2k}$$$).
Understood, thanks!
Making one decision at any vertex of the cycles forces your decision for all others. You basically choose in which direction the cycle goes.
A and C were good problems. I was not able to understand B.
problems were good, but statement was too bad
morningforces
Anyone can explain me div1A via testcase
Rating change when??
The meaning of Problem B is quite ambiguous to me. I've dedicated an hour to analyzing it.
Div.1 E actually boils down to this ucup problem. The last part of this problem is weaker than the ucup problem, so you don't have to do all the data structure problem solving by yourself.
However, since it's only the last part of the solution while the whole analysis is original, I guess it's still OK. Though maybe this sort of problem is too well-known and is trivial to many participants without seeing that ucup problem.
To add something, I guess this sort of problem along with the link-cut tree solution became well-known after Dancing Elephants in IOI
20212011 (problem, discussion), which is much similar to this Div1E. (edit: oops!)if my brain doesn't fail me, it is a problem from IOI 2011 :)
I can relate to people who struggling on div2B, including me. But now im starting to think that maybe my reading skills are not good enough. You know, theres a lot of people who have lower rating than me can did it, so why cant i? definitely need more works to do.
Anyways, thanks FairyWinx and the other authors for the round!
Can someone please explain me problem div2 B on this test case please? 3 1 6 7 9
Now you have 6 , 9
Sad, was not able to solve it in the contest. :')
what is B?? why a[n+k /2] — a[n-k /2] ?? i dont understand the question
may be problems were not that good but a lot of effort goes into conducting these contests, and we can at least appreciate that.
Am I the only one who didn't understand the Div 2 B problem?
For F there's a conceptually easier solution with the same complexity using broken profile DP. The main idea is that you make a dp over rows, and then over columns. You decide the state of each grid cell one by one, and you need to make sure you know the state of some grid cells that influence the grid cell you are currently deciding. It turns out you can use a bitmask of the following form:
So a rolling bitmask of $$$n+1$$$ bits and the first bit of the previous row. So you have $$$ \leq 2^{n+2}$$$ states. You can easily see you can recalculate this bitmask when the $$$X$$$ cell gets shifted, and you always have access to the bits $$$j-1$$$,$$$j+1$$$ and $$$j$$$ $$$\mod n$$$, to transition with the right costs added.
I think this and the easier copy-paste solution to E make the round really unbalanced, as the hard end has a lot of problems which have alternate much easier solutions. And for C and D the hard part can also be copy-pasted / is just a trick many have seen before.
I am having a hard time trying to prove that the only constraints on the flows at any stage are on the sum of subsets. In particular, why are the only non-redundant constraints on flows in form of constraints on subset-sum? Can there be a non-trivial constraint with non-binary coefficients? Does anyone have some material I can read up?
A nice blog by errorgorn explains a way to use the mincut = maxflow theorem for these kinds of problems: Mincut Blog by Errorgorn
Thanks!
In 2B, there's another way to prove why $$$f(x)$$$ is minimal at the median. We know that $$$|t|+|u|=|t|+|-u|\ge|t-u|$$$, and equality happens iff $$$tu\le0$$$.
Let's say we have $$$n=2m$$$ open bars at locations $$$a_1\le a_2\le\cdots\le a_{2m}$$$. The case where $$$n$$$ is odd is similar.
Then,
Equality is achieved iff
which is equivalent to the final range $$$a_m\le x\le a_{m+1}$$$ (a range contains all the ranges below it; that's also why we rearrange the terms earlier: to ensure equality is actually achievable). In the case where $$$n=2m+1$$$, the final range is reduced to $$$x=a_{m+1}$$$.
Guys, I know the problem statements framing is poor, but it still takes effort to present you with creative problems. Don't mass downvote, it's sad to look down on someone's efforts. Also a suggestion to problem setters — Please use chatgpt or ask your friends who knows english well to convert your problem idea to a proper statement(Obsly only who think if the statement is understandable by the lot).
Does anyone have a very clean way to code Div1C? My solution was very convoluted, needing to template extended euclidean, crt, and pollard rho, along with a lot of lines of math to get the crt mods coprime
I have a general snippet which handles not necessarily coprime chinese remainder theorem. It basically only uses the extended euclidean algorithm as a component, you don't need to factorize the numbers. 317358299
I included some code for handling 2D geometry but in the end it wasn't really needed.
Why downvote?(
idk, it was a good contest imo, thank you for preparing
Most likely the large part of downvotes comes from low-rated crowd that doesn't know the basics of math.
Don't you know?
I also wonder why.Is it because Div2B's description is too confusing?Maybe you can send a new post to collect the reason
Mid-2th Disease is PEAK
Thanks for the contest, liked the DIV2C.
the 3rd sample of div2 C really frustrated me, anyone help?
In this structure, at least one is correct.
What the hell? You dont even want to give us solution codes?
Regarding Div1B/Div2D: How did you come up with using this graph algorithm to solve it? Is this a general technique?
I don't understand the solution of Div1 B. Why doing this way?
Tried B, hell of a task just to try'n understand question only, once you know what it's asking you can reach to the core idea maybe in 10-20 mins, but the framing should have been better.
can Someone explain solution of Div1A ?
Is it possible to solve Div1A in Python? My code is identical to the ones passing in C++ or C#. Runtime is PyPy 3.x.x. Still getting TLE.
can anyone in this workd div1 A explain easily this ?
What is the best way to use bitset in Div1D? From reading code, it seems that people either use custom bitset implementations, or some iterative way of setting the length of the bitset, but I don't understand why those are valid. Is there a tutorial anywhere that explains this?
Bitsets must be fixed size. For easy implementations, one can just use a dynamic array of size $$$N/w$$$ and do the operations accordingly.
Div2E/Div1C:
Can somebody please explain how to come from this to what the original CRT solves:
Ok, t -> x, n -> n1 = n2, n — x -> a1, n — y -> a2. But what to do with vx and vy?
Perhaps you need to take a look at the Extended Euclidean algorithm (exgcd).
Could you please tell me where I made a mistake? Thank you very much. 317531940
Maybe you should give us the correct code.
Prob A div 1 :
i dont understand how is my code wrong ? 317558821
Expected YES found NO
In the For loop condition while checking for the same , greater than by 1 or more part, when the current element is greater than previous element by more than 1 , we should also check the cnt4 of the current element. If we don't we might skip it and move to the next element.
Your code
Modification
appreciated , thanks
bros contribution became -98,only for hosting this contest.
Yeah
How to prove the O(nlogn) solution for Div1.E?
Although the segment-spilt part is easily to be proved O(nlogn),but the segment-merge?
These segment trees work in $$$O(n \ log \ n)$$$ amortized. The potential is the total number of nodes that trees have.
Then segment-split creates no more that $$$log \ n$$$ additional nodes.
Segment-merge works in $$$O(common \ vertices)$$$ and deletes that exact amount of nodes.
This is an amazing contest, it helps me realize a lot of things. I have a question: what is Div2B even talking about? I just don't understand are we finding x that f(x) is smallest compared to all subset(open bars) or f(x) is smallest only compared to its own subset. Thank you for answering me.
Div1E: "For more details, you can read the author's solution." But where can I find it?
It's a bit tricky to update segments and detect when they finish. Could someone explain how to implement the Editorial solution?
1E is the same as this problem.
DIV2C(DIV1A)
Can someone help me explain why my code doesn't work?
https://mirror.codeforces.com/contest/2098/submission/319716051
Thank you very much...
319833751 sqrt solution for E. Not even all that squeezed. For small $$$D$$$, I do DP on sqrt-sized blocks "if a prefix was covered, how much more to cover the whole segment and what prefix of the next segment will it cover" and compute greedy covering quickly over blocks. For large $$$D$$$, I simulate greedy covering directly using info "find next active element or say it's more than sqrt further away".
Can someone explain 1E link-cut tree solution?
[Sorry for necroposting]
Alternative solution to Div1F without using DP. Construct the flow network only for the first day. Run Dinic to find flow from $$$s$$$ to $$$t_1$$$.
Add edges from day $$$1$$$ to day $$$2$$$. Run Dinic to find flow from $$$t_1$$$ to $$$t_2$$$.
Add edges from day $$$2$$$ to day $$$3$$$. Run Dinic to find flow from $$$t_2$$$ to $$$t_3$$$.
Add edges from day $$$3$$$ to day $$$4$$$. Run Dinic to find flow from $$$t_3$$$ to $$$t_4$$$.
...
Very close to TL, but fits without any DP and is easy to code. 328939831 (copy-paste Dinic from a template)
Is it normal for harder problems to have tight time constraints, or was Div1D just an anomaly? My
vector<vector<bool>>implementation of the editorial TLEd.Am I wrong or does div1A (Sports betting) solution has a typo. In the statement: "If sx+1≠0 or sy+1≠1, then Vadim can definitively convince at least one student on day x or day y"
It should be sx+2 not equal to zero instead of sx+1
In 2097F - Lost Luggage, you can fit Highest-Label-Preflow-Push into the time limit (if you don't recompute the flow from scratch in each iteration, but instead just reroute the excess from the old sink to the new sink). 334089270
I think there's a typo in div2C: s_{x+1}...s_{y+1}s_{y+2} — the seating arrangements from day x to day y — this is fine, but later it follows "If s_{x+1} != 0 ... then Vadim can definitively convince at least one student on day x or day y" Shouldn't it be s_{x+2} != 0 as predictions on x day are (s_{x+1}, s_{x+2})={(0, 1), (1, 1)}?
Also in statement "which is the only case where Vadim has no winning strategy according to the previous point, when n <= 3" I agree that there's no winning strategy in n<=3 case with this configuration, but when n>=4, it boils down to the winning strategy as from the 1st bullet point, a_i+1<=a_{i+1} (no breaks argument).