Hello, Codeforces!
We are glad to invite you to participate in Codeforces Round 1048 (Div. 1) and Codeforces Round 1048 (Div. 2) on Sep/08/2025 17:35 (Moscow time).
The round will be rated for everyone. You will be given 6 problems and 3 hours to solve them in both divisions. Some problems will be divided into subtasks.
The problems were authored and prepared by installb, wjy666, tarjen, StarSilk and 2014CAIS01.
We would like to thank:
- maomao90 for his great coordination.
- Alexdat2000 for Russian translation.
- Um_nik, EvenImage and SSerxhs for red-black testing.
- A_G, -skyline- and __baozii__ for red testing.
- fishy15, oolimry, Boboge, Nanani, shstyle. and Tobo for orange testing.
- qsmcgogo and Retired_Zhisheng for purple testing.
- Husqqqq for blue testing.
- jellybean259 for green testing.
- akqxolotl for grey testing.
- MikeMirzayanov and KAN for the great platforms.
The scoring distribution is below.
- Div. 2: $$$ 500-1000-1500-2250-(2250+750)-3500 $$$
- Div. 1: $$$ 500-1250-(1250+750)-2500-(2750+1500)-4250 $$$
Good luck to everyone! (=^･ω･^=)
UPD：Unfortunately, it was discovered very lately (2 hours after the contest began) that the statement of div2D/div1B was missing an important condition. The correct statement should include the line "The operation 2 can only be applied at most once." The statement will be corrected soon.
We believe this issue affected many participants of this round, and therefore we have to declare this round unrated. We sincerely apologize for this mistake.
https://mirror.codeforces.com/blog/entry/146176 please refer to this blog for more information on why we decided to make the round unrated, and further elaborations on how this accident happened. We are deeply sorry for disappointing everyone, and we hope for your understanding.
UPD2: Here's the editorial: https://mirror.codeforces.com/blog/entry/146172
StarSilk orz
As a fan of StarSilk and tarjen, I tested. Hope you will enjoy the meow meow problems (=・ω・=)
As a tester, I apologize for not finding the mistake in the statement QAQ.
!!!!!!!
Wish I'll back to GM after this contest AwA
Well, base on my experience, I do think coming back to GM is extremely difficult
And extremely easy to fall back
Oh it's unrated due to the problem B. I'm getting very angry with it.
After a long break I have started coding again to participate in this contest. And i wish i will go to expert.
As a participant i wish some dp problem.Then it will be great for learning dp.
Ready for (=^･ω･^=) meow meow problems for this contest :)
I must should and have to master dp!!! But hoping it will be nice contest
As a participant, I wish I could solve at least one problem
I wish you could solve all
akqxolotl is unrated/Black how can he do Grey testing?
Chill with that racism buddy
anyone has an advice for me to help me reach expert
anybody i am struggling with my rating i want to increase any suggestion me give
orz
what this orz
its just a symbol written through letters ,a person kneeling if you see orz
So few blue/purple testers seems a bit alarming. Let's see if the round turns out to be a speedforces.
YES IT IS
either i've become stupid or there are too many cheaters i dont understand the meaning of all this tolerance towards them
Same!!!
Wow that was clutch
Ig it's good to me that it was unrated lol. I was rank 6k
same, I was rank 5k.
Nice username
WHY UNRATED? WHO DID IT AFFECT? A BUNCH OF NEWBIES???!!!!!
bro, anyone who is less than yellow is somewhat considered a newbie.
Do you have a ton of testers and couldn't notice it? Why did you make the announcement after 2.5 hours? Why do you think many people are affected by this? A lot of people have successfully solved this problem. Why is this unrated?
At the first time when I solved E2 in div2, it is unrated :(
As of now the AC rate for this problem is at around 30% which shouldn't be (especially for a div2D) and also nearly 4k submissions, do you think 4k (or I should say 2k — 3k) people is a small amount?
Many participants spent quite a lot of time trying to solve $$$D$$$, which they could have instead spent on a different problem and solved? Therefore it makes sense to make it unrated?
They probably didn't realize this, a ton of people just assumed the 3 2 1 condition was complete, proof by AC. If you got stuck on the 3 4 1 2 condition, your contest is basically doomed, as it is significantly harder to code, and will also never pass.
Wow, glad to know this.
How did all the usual top LGMs also miss this lmao
Did they assume Div 1B to be inherently easy?
Intuitively the reason a 2 swap would save a move is by moving two numbers over another in the middle, which requires 3 2 1 to happen. However, 3 4 1 2 bypasses this by having the first move create a possible 3 2 1
That looks pretty affecting to me
But does that "However, you can only perform operation 2 at most once." affect problem D in any way?
If you perform op2 twice, you can solve (3, 4, 1, 2) -> (1, 4, 3, 2) -> (1, 2, 3, 4) in two moves, less than 4 times' op1. However, if perform op2 less than 2 times, the ans is still 4 moves.
Well so that happened.
can i get 298 upvotes instead?wow !!!
which extension? carrot?
Hey misty , could you tell me what extensions are you using for rate predictions ?
its carrot
bro it was my best contest and suddenly it is now unrated what a bad contest bad testers
Its so sad, but congrats you did so well!
omg is that sujay konda
Why Unrated?? I solved Problem E for the first time during a live contest :'(
OMG, unrated!?
man what the fuck got 2k rank for first time and this
I don't see how the other statement of problem D would convey different meaning to participants.
In the original statement — 3 4 1 2 is not perfect as you can swap 1-3 and 2-4 by using two operations of type 2
How did so many people solve Div1B/Div2D without atmost once condition?
I still don't get it, why that condition is needed
for conditions like "3 4 1 2" you should output no instead of yes. by swapping 1 3 and 4 2 you can do it in two times
one needs to check for presence of >=3 length decreasing subsequence, many didn't consider the case where this fails
I had this solution but it fails on pretest 2. Can anyone help me debug the issue? I hope it's not an embarrassing oversight.
https://mirror.codeforces.com/contest/2139/submission/337619400
Your second_greater_before logic only encodes half the condition (the left side).To be correct, you also need the nearest smaller on the right. take this test case 1 5 1 5 4 1 3 2 1 5 answer should be "YES".
Thanks, I should have tried debugging it instead of bailing and wasting time on E1. AC: https://mirror.codeforces.com/contest/2139/submission/337667179
the secret ingredient is: I accidentally solved the "atmost once condition" problem instead
My previous incorrect reasoning arose from the existence of a decreasing subsequence of length three (e.g., 3, 2, 1) within the [l, r] interval, which would force using two applications of operation 1 instead of one operation 2. This coincidentally aligned with the case where operation 2 is allowed only once. However, I overlooked that a sequence like 3 4 1 2, after a single operation 2, becomes 1 4 3 2, which leads to another invalid case [4, 3, 2].
The testers are there for a reason...
fr fr
whoa I made a comment on this post a while ago and it vanished !!!
BTW how come authors realized such big problem so late.
Can someone explain in what way the newly added condition affects some solutions for D1B / D2D? I don't get it...
In the original statement — 3 4 1 2 is not perfect as you can swap 1-3 and 2-4 by using two operations of type 2
test 3 4 1 2. In correct statement answer YES. But if you can do operation 2 more, you can do swap(3, 1) and swap(4, 2) so you will have 1 2 3 4 and answer NO.
I was stuck on this case for 2 hrs now I realise why my code is wrong.
So Why the rating3000+ user can fast solve the problem with the error statement? I cant understand.
maybe because high rated users rely allot on their intuition over formally proving each solution they come up with, at least till div1C. Others try to formally prove the problems they consider difficult ,eg:div2D+.
You got to be kidding, spent 2h thinking about this Div2D, trying to find the bug.
same LOL
Same +1
guessforces
As a participant who solved 5 (actually 4.5) problems during the contest, I am upset that the round became unrated :(
Relatable
le me: finally, i am elitist
le universe: u sure about that
still cool questions.
Changing the contest to unrated is not fair for people who did not even attempt that question, some other solution must be made for this issue
my first 3 AC in div 2 OMG
I finally get cm perf and this happens, are you fucking with me.
It should be unreated for those who want it, I even did the problem c quickly for the first time :(
there goes my hope of recovering my rating from this round.
Man i skipped my dinner for this quess,i would have become a specialist today (╬▔皿▔)╯
Nooooo, my CM :((((((((
damn why unrated ，wasted my time.solved the problem and get not bad rank.also that isnt important if the operate2 only can use once，i didn't know that but accepted the problem.
You found wrong solution for the problem without the new condition
Actually, if the operate2 can be used several times, the solutions used by most participants are wrong.
The fact that over 70% of Div1 contestants solved B by guessing a completely wrong solution is actually insane.
whoa!!! how is this possible
I find the solution quickly but soon find it wrong when "3 4 1 2"
Same, man. Same.
not solve it until I see the notice
guessforces,bestforces
AND SPEEDFORCES
I lost my chance to get +100 delta & reach rank ~20 in a rated Div. 1 round...
Well, technically you reached this rank
It really feels pathetic to spend 3 hours in a contest..just to find out the question you were stuck is wrong and the whole contest is declared unrated
It's unnecessary to make the contests unrated.
Yes, but at least unr for who doesn't solve div1 B. haha
never in my life solved an E problem. when I finally did, the contest turned out to be unrated, so cool
what you are taking about contestant unreted i don't understand
Messed up C with 2WA, I thought I had clutched D and was feeling really good about myself, only to be faced with WA.
Are they actually deleting blogs where there are suggestions about how to deal with this situation??
[div1. B] When operation 2 can be used any number of times, a sequence b is perfect if and only if it is both 321-avoiding and 3412-avoiding.
I wrote a brute force solution and, through experiments, discovered this fact. However, when I tried to implement it (which was difficult!) and submitted it, I got WA. Stress testing didn’t reveal any failing cases, so I was stuck.
Then I thought, “Could it be…?” and tried submitting a solution that only checks the 321-avoiding condition — and surprisingly, it got AC.
I think many people’s solutions would fail on the following case:
can you please tell how you brute forced min swaps for operation 2 ... for operation 1 I know it is inversion count.
It’s just a simple BFS. Since it’s enough to run it only on small cases, I allowed it to take O(N!) time.
ok!!! Thanks for telling me. Makes sense.
Do you have a proof that "321-avoiding and 3412 avoiding" is truly a necessary and sufficient condition?
I haven’t proved it, but through experiments I confirmed that it holds for many small permutations (with N<=10).
came here to ask the same thing ! All I was able to prove was that :
for the largest element that hasn't been sorted which is currently at index i in vector v:
then this is sufficient to say that g(v) != f(v) as I could swap elements at i+1,i+2 with a 2-jump and this would be optimized for E's sorting as I would do 1 jumps until E reaches i then do a 2-jump again to re-sort it.
now that I see this is technically the 3412 condition and It is obviously sufficient. can't see why its necessary yet !
And btw how can you determine if the given sequence contains 3412? Weird segtree?
Yes, my code uses a segment tree.
337628359
3412 would be just 4 consecutive elements or there would be 321 if they're not consecutive
consider the case 4,1,5,2,3. [4,5,2,3] are "3412" but there is no "321" but they aren't consecutive and yet our optimization would work :
[4,1,3,2,5]
[1,4,3,2,5]
[1,2,3,4,5]
we did in 3 steps compared to the number of inversions (g[A]) = 5
Changing the contest to unrated is not fair!!!!!
If not change the contest to unr, it's also unfair to the one who doesn't solve div1 B because of the missing conditions.
But what about the time and effort we already spent on the contest، Isn’t that also unfair???
I know right? Genuine skill issue, the people commenting for it to be unrated wouldn't be doing so if they got AC...
At least make the round unrated for those who want it.
Yes, I agree. If some want it unrated, let it be optional, but don’t make it unfair for everyone.
https://mirror.codeforces.com/blog/entry/146176
I am very sorry about this issue. I wrote a short blog explaining the issue. I hope that everyone will downvote my blog instead of the announcement, as the authors worked very hard for this contest to happen, and it was fully my carelessness that resulted in this issue.
in editorial, write solutions for both variations .. ha ha !! because I want closure on spending so much time on div2D
Auto comment: topic has been updated by wjy666 (previous revision, new revision, compare).
Alr go installb, wjy666, tarjen, StarSilk and 2014CAIS01 are yall blind? Smart guys.FKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
what is proper way to find min operations for div2C
I guessforced by going in opposite direction and always taking from greater one... but I feel there is some observation in bits to be made ?
your guess is certainly right
yes, thanks.. but couldn't prove — why it always reaches the solution and — why this is minimum
I only submitted coz it was passing given cases.
Ohh. I tried to check if the total of the new values is == 2^(k+1) and if a < b then take from b and if b > a then take from a else end.
yeah I think same same
Take the larger piece between x and 2^(k+1)-x; the minimum number of operations equals the distance between its leftmost and rightmost set bits.
To construct the operation sequence, traverse the bits from MSB to LSB, toggling between sides (1 and 2) whenever curr and next bit differ
ok,thanks !! I will think about this next morning.
At some step, let's say player 1 has x and player two has y and wlog, x < y. We have two cases for the previous step. If player 1 gave half in the previous step, then prevX = 2*x, prevY = y-x.This case is possible. If player 2 gave half in the previous step, then prevY = 2*y, prevX = x-y. But we assumed x < y which implies prevX <0 which is not possible. So, there is essentially only one option at any step if we go from backwards. Now, we haven't proved that we will be able to make x and y equal but in the problem they mentioned that it will always be possible in atmost 120.So, I didn't bother proving it xD.
ok, thank you.
I also didn't prove my approach ha ha!!
I really sad. I'm solve ABCE1E2 in first on my life and i gonna have +80...
how to do div2 E2
Using bitsets for subset sum dp
oh wow I did part 1 using subset sum.. should have thought more.
thanks for telling me this solution.
Since the contest finished I can write now (there is a spoiler for problem D)
How did the change affect the problem? If you use the second operation any number of times (or at most once) the answer will be the same! So if you write at most once or not it doesn't matter. Why you made it unrated!
It's certainly necessary.
in the situation
If the operation2 can be used several times ，the answer should be No.If it can't, it should be Yes.
is this some kind of a joke?problem statement changed at the end of contest?
Is there anyone else like me trying a bitset in C2? Bitset is an intended solution, or is 6s just a trap?
My bitset code: 337632742
Dude your code TLEs, I think the intended solution is FFT
bitset works. https://mirror.codeforces.com/contest/2139/submission/337651932
the intended solution is the O(N sqrt N) knapsack dp I believe, but I got baited into bitset too. should probably work with good enough constopt though.
huh what is O(N sqrt N) knapsack dp
Here's a rough explanation:
We assume $$$W=n$$$, so $$$O(nW)$$$ becomes $$$O(n^2)$$$,but this trick also works otherwise and allows for O(W sqrt W) knapsack. An interesting trick is that 3 copies of a number $$$x$$$ can represent a choice between increasing by $$$0$$$, $$$x$$$, $$$2x$$$, or $$$3x$$$. However, there exists an equivalent way of being given this choice, which is having 2 elements in the knapsack with values $$$x$$$ and $$$2x$$$. Since this choice removes a net total of 1 element, this speeds up the knapsack. This process can be iterated, and so only at most 2 elements of any value $$$x$$$ must remain. In other words, there must exist at most 2 copies of 1,2,3..., and in fact you can use this to show there must be at most $$$O(sqrt N)$$$ elements in total. In general, for the general case of having sum $$$W$$$, this reduction allows at most $$$O(sqrt W)$$$ elements to remain.
apparently the constopt in question is finding the next set bit in the bitset in O(fast) (specifically, faster than a linear scan), which would've worked.
Contrary to the authors' claims, $$$3,4,1,2$$$ is not actually a countercase so I have no idea what fails D as previously written but passes D as it is right now, and I don't think the authors do either.
(3 1 4 2), (1 3 4 2), (1 3 2 4), (1 2 3 4)
4 swaps total
(3 2 1 4), (3 1 2 4), (1 2 3 4)
3 swaps total, better so no (same as answer in the other case for D)
An actual wrong test case would require multiple op 2 swaps to save 1 or more moves, but also that 1 op 2 move cannot save moves.
EDIT: somehow messed up my op2 case, yes the op2 case takes 3 operations regardless of which op2 you take since it only fixes 1 inversion. Unfortunate :(
your op2 swap is wrong
yep I noticed, my bad this is what happens to my brain after a 3hr contest...
The countercase stands.
Your example of doing 3 swaps is wrong. Notice you went from (3, 1, 2, 4) --> (1, 2, 3, 4). This is not a result of doing either operation 1 or operation 2.
Since the statement of d2D/d1B changed to only allow at maximum 1 operation 2, the 3-4-1-2 case is wrong, therefore we only need to factor in the 3-2-1 case (which makes the problem much simpler to implement). I actually just deleted part of my code at got it AC.
Okay problem, but it was a pity it had to be this way.
First time cracked Div2C in live contest! Yayyy!!! I was happy until I saw that statement 'We apologize'
Me whole 2 hours :-
I can solve E1(trying dp[node][no. of zeros left] -> Nah i can solve D Segment tree? Nahh dont know -> again back to E1.
I don’t really understand why the contest was made unrated. I’ve been trying to think of a case where limiting operation 2 in problem D to being used at most once is important, but I haven’t found any.
From my perspective, the key point is whether we can reduce the number of inversions in the array. If this can be done with a single operation, that’s already enough. This seems like an observation that contestants should make during the contest, rather than something that must be explicitly stated in the problem statement.
mentioned here — https://mirror.codeforces.com/blog/entry/146176
Thanks u for sharing!
thank god it was Unrated.. just solved one problem lol
I don't get the point of making the contest unrated. Some other workaround could have been found.. like removing the points of problem D. I got a good rank today after a long time. Codeforces has recently become an uphill battle.. first fight against cheaters and then this happens.
it would still affect people who got stuck on problem D thinking it was their fault, which makes the later problems harder mentally AND give less points
Many people will spend time on div1B/div2D, too many people to not make top ranks completely unfair if it's removed.
Would you mind explaining why you divide D1C/D2E into 2 subtasks? is it necessary to create a special subtask for bitset?
there is another soln, you can split k objects of same cost to __lg(k) objects but I agree (also I'm mad my last minute sub got WA32)
I know that, but I think two sides of the coin are wrong — they create a subtask for bitset, or they did never know bitset could pass pretests in 1/2 TL...
I don't think squeezing bitset is the intended solution, you can instead:
Observe that if the minimum depth of a leaf is $$$x$$$, the answer is always $$$x - 1$$$ or $$$x$$$.
Do knapsack to check for $$$x$$$ in $$$O(W \sqrt {n})$$$ time since there are only $$$O(\sqrt{N})$$$ distinct counts of nodes per depth (since they sum to $$$n$$$). (basically the trick described in this blog)
Though I'm still 50/50 myself on whether even this really requires a seperate subtask.
You can do it without squeezing or making the observation that answer is $$$x-1$$$ or $$$x$$$. You can write a bounded knapsack for this. My submission
The last minute change on D was really an a-hole move ngl.
A round being unrated almost at the end of the contest is such a slap in the face.
Ok so my solution of E is surprisingly simple. Figuring it out, on the other hand... wasn't simple at all.
Main idea: tridiagonal matrices. The determinant of any top left square $$$i \times i$$$ of such a matrix is given by a simple recurrence: $$$d_i = d_{i-1} a_i + d_{i-2} b_i$$$, with $$$d_0 = 0$$$, $$$d_1 = 1$$$. In this case $$$a_i, b_i \in \left\lbrace -1, 0, 1 \right\rbrace$$$.
Let's simplify it even further: we take a matrix with 0/1 on the diagonal, -1 above it and 1 below it. We just need to choose the right bits on the diagonal — there's $$$2^{50}$$$ options so it should be enough, right?
The formula simplifies to: if 1 is on the diagonal in the cell $$$(i+1, i+1)$$$, $$$d_i = d_{i-1} + d_{i-2}$$$, otherwise $$$d_i = d_{i-2}$$$. (The top left cell is always 1 for $$$d_1 = 1$$$.) Going in reverse, we either subtract or swap. That's Euclid's algorithm — the slow version. We know $$$d_n = K$$$ and for any $$$d_{n-1}$$$ we can simulate this in reverse and obtain $$$n$$$ — the size of such a matrix.
That's a lot of values! However, we know that short sequences arise when $$$d_{i-1} / d_i$$$ is approx. the golden ratio $$$\phi$$$. What I did was simply trying all $$$d_{n-1}$$$ close to $$$K \phi$$$ and picking the smallest $$$n$$$ among them. It's slow for E2, barely fitting in the time limit for the matrix size limit, but hopefully good enough.
I also reduced $$$K$$$ to an odd number and added diagonal blocks ((1, -1), (1, 1)) with determinant 2 at the end, but that shouldn't affect things much.
And now it's time to figure out if the change in B affected me. I misunderstood things in the problem, but they were different things.
Noooo i did so well and it became unrated sad. Anyways still a good round
+1
What？Can I choose to be rated?????Thank you!
Div1A is a known problem, even solved by a minecraft youtuber: https://www.youtube.com/watch?v=AdHGmFpaoCE
ohno，unr，The tester's mistakes should not be borne by the contestants.
I was so happy about getting a high rank this time, but it turned out to be for nothing.
give me my 3 hours time back !!!!! I gave a contest after almost 2 months and was satisfied doing A-C!!!
All the testers should be banned , it seems they didn’t even test problem D
I just had the worst luck. I was gonna reach Specialist for the very first time today, on my 100th contest. I have two exams tomorrow and bunch of studying to do. Still I sticked around for 3 hours and pariticipated. All for nothing.
Man,I solved E for the first time and contest got unrated :/
Is Div1D something roughly along these lines:
(notation: $$$i$$$ here refers to the slider targetted by the query and $$$j$$$ to the slider for which we're calculating the sum)
A. $$$f(p_j)$$$ could be any position reachable by
performing any move for slider $$$i$$$ (if there exists a move for slide $$$i$$$).
performing one move for any other slider (optional if we performed a move for slider $$$i$$$)
lets call the number of the final moves in either case the number of equal elements.
B. Any move which would cross $$$f(p_i)$$$ must be performed BEFORE the moves from (A) — lets call this the number of greater elements. You can compute the numer of such moves for a certain f(p_i) using a difference array with ranges of the form [1, x + (j — i)) or (x + (j — i), n].
C. So the answer for placing a slider at a certain position is something like ways to order the greater elements ($$$cnt_{gt}!$$$) * ways to distribute the equal elements depending on the two cases in point 1 (bars and stars) * ways to place the other smaller elements ($$${q}\choose{cnt_{gt} + cnt_{eq}}$$$).
(I know there are a lot of details which are vague or outright missing, but is this very roughly in the right direction?)
I went in a different direction, since fixing the final position seemed difficult
find number of permutations where you end up >= some position
An editorial would heal some wounds:)
I just want back to expert,but it unrated, so sad :(
In Div2 Problem D, I'm trying to understand the relationship between two functions, f(b) and g(b).
g(b) is the value after applying only type 1 operations. f(b) is the value after applying at most one type 2 operation in addition to type 1 operations according to the modified statement.
Type 2 operations always decrease the value of as compared to g(b). Since one type 2 operation lowers the value, applying more would lower it even further.
Can anyone clarify under what circumstances this might not be the case? For example, would "at most one" operation fundamentally change the relationship between g(b) and f(b) compared to "one or more" operations?
If the array is [5 2 3 4 1] and we are only allowed to use at most one type 2 operation and any number of type 1 operations, then it will look something like this:
5 2 3 4 1 -> 3 2 5 4 1 -> 3 2 4 5 1 -> 3 2 4 1 5 -> 3 2 4 1 5 -> 3 2 1 4 5 -> 3 1 2 4 5 -> 1 3 2 4 5 -> 1 2 3 4 5 (total 8 moves)
And if we are not allowed to use a type 2 operation, then we will simply send 5 to the end and 1 to the start using 4+4=8 operations... thus, in this case, using a type 2 operation didn't save us any moves because it made the position of 3 wrong.
It's not necessary to use the type 2 operation in the first move, right? In your example, if it is allowed to use type 2 operation, I will go with 5 2 3 4 1 -> 2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 1 4 5 (used type 2 operation here)-> 2 1 3 4 5 -> 1 2 3 4 5 Which took 5 moves. Basically, during the process of swaps, if there appears a subarray in the format [c, b, a], the type 2 operation can save the moves by doing [a, b, c] in a single move.
5 2 3 4 1 -> 2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 1 4 5 (swap 1 and 5 using type 2 op) -> 2 1 3 4 5 -> 1 2 3 4 5
5 ops
Using only type 1 operation — 4 ops to send 5 to the back, 3 ops to send 1 to the front
Won't using a type2 op save moves?
Is it possible to just remove D and calculate the ratings ? Please dont downvote me out of frustration.. I am just asking out of curiosity
As I said above: Many people will spend time on div1B/div2D, too many people to not make top ranks completely unfair if it's removed.
For Div2 C, what's the answer for k=5, x=21?
5
1 2 1 2 1
Just try to make $$$x = 21, y = 2^{5 + 1} - 21 = 43$$$ to $$$x = y = 2^k = 32$$$:
$$$(x, y) = (21, 43) \longleftarrow^1 (42, 22) \longleftarrow^2(20, 44) \longleftarrow^1 (40, 24)\longleftarrow^2(16, 48)\longleftarrow^1(32, 32)$$$
Then you can get the answer by reverse the sequence "12121" -> "12121"
They did make a mistake, but believe me, the only way to fix it is to make the round unrated. People who understood the problem correctly were at a disadvantage, while surprisingly, those who misunderstood it were the ones who solved it. That’s just insane.
You know what could also be fair? Calculating the ratings only for those who want them to be counted (since they all performed well). But this would mean that even if your rating was supposed to increase before, it might now decrease, since you’d be competing with a smaller group
Making the round rated only for those who were going to get +ve delta could be a solution. Couldn't it?
But if you only consider those people, some who would have gotten a positive delta would end up with a negative one. If you mean only giving out positive deltas, that’s basically just handing out rating boosts, which I think could negatively affect the overall balance of the ratings
firstly ,cant believe the testers also assumed a wrong solution to D , have college exams after 2 days ,wasted 3 hrs on this secondly , is there a solution to the wrong ques btw
337624531 For E1 why i hv wrong on test 4 .... (my idea .. take the first consective levels by their whole nodes till i can't)
I retract my previous statement. Mistakes happen.
Bro, chill. It’s just a contest, we compete to solve problems, not just for ratings. The problems were overall nice, and personally, I enjoyed them.
The contest was AMAZING even though there was a little issue. Thanks to wjy666 and the whole team for their great work!:)
Why they said the contest is unrated? At least give us rating of what we have done in this contest, the peoples who solved problem D will be not happy with this
does this solution work.. if it does .. then why?
i came up with this solution when the contest was live.. but then a thought came into my mind.. what is happening to the remaining seconds when m>n .. i did not notice that my solution is already working for such testacase( case 1 from the given cases ).. so i did not submit.. cause i am a dumass ofcourse.. but yeah why does it work
your loop breaks (when m>n ) before m gets negative, so only larger values of m are considered ,before that time all cakes gets accumulated.
Despite the unexpected error, D1D/D2F, the only problem StarSilk proposed in this contest, was very profound and ingenious.
We are all human and we all make mistakes, but the way this mistake was handled is very strange.. making the contest unrated for everyone?? I understand that if it had stayed rated, it wouldn’t be fair to those who couldn’t solve the problem because of the missing condition, but what about the people who performed well on the rest? What about those who didn’t even attempt that problem at all? Someone like me usually target solving A, B, and C, and today I managed to solve them in good time, and according to Carrot I would have gained around 40 rating. So this is completely unfair to me, forget about me, what about the people who were about to reach a new rank after working hard for it for a long time, only to be told in the end that all of that was pointless?! The right way to handle this situation is to keep the contest rated for everyone but ensure no one loses rating, that would be the fairest decision and would cause the least harm compared to any other option in a situation like this.
Agreed
How will you differentiate between someone who skipped the question and someone how wasted may be entire time on the question ?
You’re right ofc, but the same logic applies if you make it unrated, because you’d be unfair to those who weren’t affected by that problem at all. In situations like this it’s impossible to achieve 100% fairness but the goal is to find the solution that minimizes the losses and that’s exactly what I meant, because this way no one would be harmed the way people would be if the contest became completely unrated.
I solved E1/E2 with binary search + greedy. Most solutions use DP. I did offline brute force check after the contest and it has held up in my checks vs a participant's solution that used DP. Thought people might find it interesting (or provide it wrong with a counter case).
https://mirror.codeforces.com/contest/2139/submission/337659972
Edit: seems the test cases are weak. Below breaks the algo.
ones=6, zeros=8 levels = [1, 3, 3, 3, 4]
I solved E1 with just greedy
why will it not work for E2?
I also solved but it is wrong na submit same solution of E1 on E2 and it will give a wrong answer.
i have thought about this but but second thought that n <= 1000 so i thought greedy would not work.
Well E2 was 10^5.
Too bad I did not submit mine during the contest :( https://mirror.codeforces.com/contest/2139/submission/337667739
After long time I solved problem C in div2 but totally got upset of getting notification of unrated due to problem D statement correction
Thank you for the round — very interesting tasks! Very want editorial with two "version" of div2D
Can we solve Div2 E1 just by greedy?
yes I solved it I dont know why it is giving WA on E2 probably there is a stupid implementation problem.I can tell you the proof of my greedy solution if you want
yes please. i wannna check whats wrong with my logic.
I found a testcase which gets wrong answer with n=13 my solution shouldnt pass E1 lol
But what logic have you used anyways?
I found the minimum depth of the any leaf node.Then I find the number of nodes on every depth.And for (2,minimum depth) the number of nodes will always increase or will stay same I think this is easy to understand.So I thought that starting from the depth 2 is optimal (depth 1 will always same for all strings.So if both number0 and number1 is greater than sz[depth] I chose the minimum one to fill that depth (ans++).If neither of them is greater than sz[depth] I ended up the for loop.So that is all
it's a shame that the situation with problem B happened. i am sorry that this blog is downvoted. problems A, C2, and D are phenomenal! i think it could be the best problem A i have ever seen :)
Are the test cases weak or does greedy work for Div2 E1 and E2? 337667308
can you please tell me whats wrong in my code/logic ?337659720
1 7 4 1 1 2 2 3 3 it should be 3 but your code gives 2 , u are always assigning zeros first, but if no. of ones is less than no. of zeros, it is optimal to assign ones first so that maximum no. of levels can be covered with minimum no. of assignments of ones .
Can you share what logic did you use ?
Doesn't matter. It is wrong.
can you please explain the greedy logic youve used?
Find the number of nodes at a certain depth until the depth of the highest leaf node. Sort it. Then greedily assign each node the number that you have the least amount of, if possible.
in problem d: will finding next smaller value index and the next smaller value index again work?
or is it different from finding a greater value index before and a smaller value index after?
There was no need to set the time limit so high in problem Div2E2/ Div1C2 if the authors didn't bitset solutions with $$$\frac{N^2}{32}$$$ to pass
Most of the solutions I have seen which uses $$$N$$$$$$\sqrt{N}$$$ solution passes within 500ms. 6 second is quite high time limit if the authors didn't want the bitset solution to pass.
I had the idea of bitset immediately after solving C1. However, I thought it wouldn't pass. I guess it's my fault after all not trying the bitset solution
How was bitset used to solve the problem ?
Bitset actually also runs quite fast
My bitset solution takes 577ms with custom bitset and 937ms with default bitset
I mean what was the logic ? for E1 i did calculate no. of nodes at each level and then used dp to find maximum number of nodes that can be painted with 1's.
Finally if all nodes till certain depth(mx) can be painted then answer is mx else mx — 1.
Basic knapsack with bitset, it should be easy to find on the internet.
Basically if we say that dp[w] = (can we get the sum of weights = w?), then adding a value $$$x$$$ looks like
which is the same as doing
if dp is a bitset.
Please hack my E2
https://mirror.codeforces.com/contest/2139/submission/337644455
There is not really a lot of reasoning behind it, when the distance to the closest leaf is < $$$\sqrt(n)$$$ I do the same solution i did in E1, but when that does not hold then the number of nodes in each level has to be lesser than $$$\sqrt(n)$$$ which allows for the relevant updates of the subset dp to be closer together.
I think this makes sense however I am unable to prove it and would not be surprised if I fakesolved this, pls help
Pretty sure that is the intended solution
You should try
\sqrt{n}$$$\sqrt{n}$$$ instead of\sqrt(n), in LaTeX, the former indicates that{n}is a whole, but the latter indicates that you have placed\sqrton(.Editorial wjy666?
Does D2E1 have really weak test cases? This greedy solution passes for E1 (fails for E2). https://mirror.codeforces.com/contest/2139/submission/337674926
The binary search is not even required for E1 as O(n^2) per test case should pass easily.
Yes it has weak testcases. I found this testcase which fails the greedy method.
1 16 4 1 1 2 2 3 3 4 4 5 6 7 7
It should be 13 instead of 16 though. And, it correctly outputs 4.
Yeah 13 my bad, my greedy was failing on this one, but yeah greedy wont solve this problem
Can't imagine why greedy will eventually pass E1... I guess your greedy is same as mine.
Mine fails here: 1 29 14 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 17 18 19 20 21 22 23
With Items when mid = 7: {6, 6, 4, 4, 4, 4, 1} divided into: {6, 4, 4} {6, 4, 4, 1}
Mine outputs 7, which seems to be the correct answer. I want to find out the smallest array for which this fails.
Found it: a = [1, 3, 3, 5], n = 12, k = 5
(0 remaining, 1 remaining) = (5, 7) initially. Here, picking the larger count for the last level with 5 nodes leads to a conflict so my solution fails.
My greedy used to fail here too >.<
yes.
I was wondering if it’s okay to have E2 with a slight difference from E1 just to make it optimal and get AC?
D is cool Problem anyways!
Stfu
As a problem, I can confirm I wasn't tested
I am new to codeforces and gave just 1 div 3 contest. I didn't know how divisions work on codeforces so I gave the previous div 2 contest in unrated mode, I came to know that the questions are solvable by my level so this was my only 2nd contest and I did pretty decently and solved 3 questions with a rank of roughly 3.5k and this gets flagged as unrated as well lol. I don't wanna sound rude but the UI sucks, people are rude to each other for no reason and now even the contests are giving out wrong questions lol I can't force myself to like codeforces rn, why is everything and everyone so gloomy here?
wasted 3hrs of my time in exam session just to give an unrated contest?
This was my first div 2 contest in which I solved till problem C, but it turns out that this contest is declared unrated :'(
When will the reate i am witing
the contest is unrated, there will be no rating changes for this contest
Ngl, I messed up so bad, that I'm kinda happy it's unrated now. Would be fair to everyone though if they made it rated and kept rating change as max(0, delta)
U mean... a tiny bug in announcement makes this contest unrated? I just wanna ask who was affected by that? ⊙^⊙
I have solved A,B,C and E1 in this contest and my rank was around 1050, I really hoped that my rating will increase to 1550 (Now 1471). Sad contest, fuck you so much.
please could someone guide me to reach pupil it has been quite a time help T-T
So if Div2 D doesn't have the "only use once" restriction,can it still be solved?
As a competitor, I tried me best and solve 6 problems, but now it became bootless:(
It was my first participation in Div-2 contest and it was made unrated :'(
why did it become unrated man
There were some problems with the questions so they decided to make it unrated :'(
Guys, what is up with the ratings?? no rating update yet, can anyone clarify when it will get updated..
There was a mistake in a question. So they made this round unrated for everyone. It's sad for us who were going to get positive delta. but there is nothing we can do about it.
when will rating of this contest get out ??
First time I solve 3 problems in div2 and it got unrated.
First time I solve 3 problems in div2 and it got unrated