你好，Codeforces！
We (FeOI and WAOI Team) are glad to invite you to take part in Codeforces Round 1035 (Div. 2), which will start on Jul/05/2025 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.
All problems are authored by lizhous, Lyz09, ma2021tyoi0037 and me.
I would like to thank the following people for making this round possible:
- abc864197532 for the excellent coordination.
- Alexdat2000 for Russian translation.
- lizhous, Lyz09, Rebex, hzy_____ and me for providing some rejected problems.
- Z-301 for Legendary Grandmaster Testing. He was promoted from IGM to LGM four days after testing, congratulations!
- Fysty, _istil and N_z__ for International Grandmaster Testing.
- zltzlt, irmuun and Misuki for Grandmaster Testing.
- SunsetGlow95 for International Master Testing.
- qwexd and myst-6 for Master Testing.
- aIish, NintsiChkhaidze and vikram108 for Candidate Master Testing.
- gza, bever209 and darysani for Expert Testing.
- hzy_____ for Pupil Testing.
- STAR_light_ for Unrated Testing.
- You for participating the round.
- MikeMirzayanov and KAN for Codeforces and Polygon systems.
We hope you will enjoy and have fun in the contest.
Score distribution: $$$500 - 1000 - 1500 - 2250 - 2500 - 3000$$$.
update 1: Editorial is out!
update 2: Congratulations to the winners!
Div. 1:
Div. 2:
Auto comment: topic has been updated by CutieSmileHaruka (previous revision, new revision, compare).
seems I should not greet the author a hello back, so I am being downvoted :(
Codeforces upvotes work in very stupid ways. I would suggest to not pay attention to it.
leave them , kindly review my profile and suggest what should I work upon , Shreyan It would be quite helpful :)
stay consistent
I enjoy cp and I have no plans to leave it :)
DO NOT ABBREVIATE COMPETITIVE PROGRAMMING NOOOOO
ok , sorry
and u have abbrevation in name?
hank do not abbreviate cyberpunk hank
yes, you shouldn't be nice to people here, the conventional rules of human society doesn't imply here.
ji verma ji
I am noob in coding rn but will try to solve at least problem A in this div 2 contest
try 2 :->
will do bro
hope my turtle hermet schooling works this time??
Bro, I just saw your profile and I wanna say that we are quite similar ;) GL to u
Hope problems be easy for beignner
no hope for div2
OMG!! Chinese round
Thanks for the contest!!!
Hope problems will be anti-AI , rather than similar to those in 1033....
The pros and cons always work on a odd way...
As an author, I hope all the contestants GL & HF!
wtf is FeOI and WAOI
Why do you use passive voice? There's no one to promote him lmao. Isn't it "He promoted from IGM to LGM four days after testing"?
Uhhh... Codeforces promoted him to LGM?
I think this contest will be full of math.
Why do you think like that?
it was a joke.
uhhh ok thx
I meant it ^_^
Wow, are you a genie or smth =)))
I hope to break my streak of negative deltas.
Also based on the score, this might be a speedforces round ... lezzgo !!!
what is the meaning of speedforces?
so 4th question generally has rating around 1750 and is solved by very less people so that decides the rank.. but in this 4th question is 2250 so will be very difficult to solve
so ranks will mostly be decided by SPEED in first 3 questions and not the 4th question ig.
also someone wrote a post about it lol -> https://codeforces.me/blog/entry/131746
so surely i should start solving from D 🧐
haha nice!!! respect.
As a tester,I think this contest is really interesting.
hoping to get CM this round, fingers crossed
I'm depressed by my recent performance
You did like 500 problems so you are probably much better than your rating and likely you just got unlucky
Probably
tbh I think its not just luck. He is practicing not much
I've been CM six times. Hope that I can become a Master this time.
i got it.
Hope to enjoy in the CN Round!
I wonder if the round is more difficult than Div.2 in Luogu.
Oh, Chinese round!!
lets goooo
haha!! you are tooourist, little son of tourist
noo. i'm just his Azerbaijani version. hahaha
hi guys, i have a question that my old accout is disabled by the administrator codeforces, the question is my old accout is banned forever or temporary, i just violate once time. Tks you guys
yea maybe stop cheating man
I wish success to all participants... My friends, you are legends.
is this a harder div 2 cause c is 1500 and b is 1000
D is expected to be hard
Points are an indication of the relative difficulty of the problems in the contest, not the actual problem ratings
From this pattern, you can conclude that speed-solving ABC is the way to go :(
usually c is a little difficult for me
yea
As a tester, good luck.
As a participant, thank u.
Always stuck on C/D...
Glad to see 你好，Codeforces！
orz Chinese round
你好，出题人！
CSP-J2025 rp++！
听取WA声一片
I think you will be downvoted soon.
OH yeah! I am ready for this new challenge
Hoping to get to specialist after this round.
As a Codeforces beginner, I'm not quite sure whether the score distribution represents the approximate difficulty gaps of the problems. Does it mean there's a high possibility that D would be significantly harder than C, or there's actually no fixed relevance between score distribution and absolute difficulty?
Good luck to everyone.
Summoning rating for this contest
hope to reach 1700+)
dear MikeMirzayanov and KAN:
my alt 16777mt16 has been banned during this contest and the submissions have been skipped. can you tell me why am i banned? because of using ai? NO, i have not used ai.
i know my actions may not match my current 'specialist' level, but i've written many, many 2800 problems and i've got a 2440 rating atcoder account(name ultvoW_mEden. i'll mark that in my AT account soon). besides, i'm very good at counting problems. i didn't want to lose too much points so i watched d at the beginning of the contest. luckily d is a counting problem so i passed it quickly.
UPD1: i participated in codeforces far less frequently than in atcoder, because i'm Chinese and most contests in codeforces are late at night for me. THIS IS MY ATCODER ACCOUNT -> https://atcoder.jp/users/ultvoW_mEden
UPD2: this account is not trusted. i hope someone can proof that my codestyle is not inhuman and my speed matches my skills. i also hope that my friends can create a blog and speak for me.
UPD3: i asked the admins to re-enable my account because that is my main account, and i'm gonna write problems on it. i'll DEFINITELY not participate in ANY codeforces contests anymore unless codeforces get a MORE ACCURATE anti-cheat system. after i get trusted by my red friend, i'll publish a blog to expose how bad the anti-cheating system is. besides, my submissions SHOULD BE rejudged and the rating SHOULD BE rolled-back.
i'm innocent. can you please PLEASE look at my program and daily practice? i'm NOT ai at ANY side.
yours, 16777mt16.
I suggest you create a new blog to explain this.
surely i want to, but i'm not a trusted user.
UPD1: now i am.
why can't i see the standings?
I watched for 20 minutes, but I didn't understand what question D meant.
I understand now, there was a problem with my translation, I misunderstood.[cry]
Seems like second problem is closely related to Goldbach's conjecture!
I solved it using polynomial inequality, like we get two eqns, summation xi*cos(theta i)=q1-p1 and summation x2*sin(theta i)=q2-p2. solve using polynomial inequality
B ruined me
rubbish speedforces. D is much more difficult than normal round.It should be placed at E.
Can you tell me the approach for D??
D is not that hard but E and F are too hard for Div2. I don't have any idea about E or F.
I think D E F is all too hard for div2.thay can become E F G.
I hate bitset problem so much like it's unreal
Really enjoyed solving D. Great contest overall.
Can you please share the approach??
Instead of finding $$$f(a)$$$ over all $$$a$$$, we can consider all sequences of moves and find the number of valid $$$a$$$s that allow for that sequence of moves. A sequence of moves $$$s$$$ can contain each number from 1 through $$$n$$$ at most once (since there is only one token for each) and 0 any number of times. It must have length $$$n$$$. Furthermore, $$$0 \le s_i \le i$$$ for all $$$i=1,2,\dots,n$$$. Here, $$$s_i=0$$$ would represent not taking a token because the current number in a is 0, and otherwise $$$s_i$$$ means take token on $$$s_i$$$ on move $$$i$$$.
There is a clear bijection between the original problem and our new system, since we are counting the number of pairs of (valid $$$a$$$, sequence of moves) for both cases. Then the answer is equal to the sum of the number of valid $$$a$$$ for each $$$s$$$ as described above.
To find this answer, we can use dynamic programming with $$$dp[p][q]$$$ denoting that we have processed $$$p$$$ and later elements, and we have taken $$$q$$$ tokens ($$$q$$$ nonzero numbers) so far. Furthermore, this can be reduced to 1D since we only care about the last $$$dp[p]$$$'s results. Can you implement this?
please tell the idea behind the solution.
Is there a solution for B which doesn't involve decimal number ( from calculating distance between start and end ) ?
I wasted some time overthinking precision issues, which I think might be un-necessary.
same
Instead of taking sqrt you can square the other side of the inequality that has to hold
Square is all you need
I agree
Do everything in terms of the distance squared, which will always be an integer
what was your condition which works with square distance, can u please tell me.
You can rotate each segment as you like, which means the points you can reach are rotationally symmetrical. Therefore, for a given set of segments, the reachable points will lie in a ring, with inner radius Rmin and outer radius Rmax.
Think about what adding each new segment does to Rmin and Rmax. You can iterate through each one, updating your ring. Finally, compare if the distance squared between the start and end points is within the square of Rmin and Rmax.
ok this makes sense, thank you.
The condition for being able to reach end is: max(0, 2 * ma — sum) <= dif <= sum
The condition above is the same as doing: max(0, 2 * ma — sum) * max(0, 2 * ma — sum) <= dif * dif <= sum * sum
So you don't need to take sqrt of dif
ok, thank you
You can use the square of distance to avoid decimal numbers.
Calculate the Min distance and Max distance you can go, and compare dis*dis with Min*Min and Max*Max.
oh ok.. i used some other condition like triangle inequality which I was not able to convert to square of distances.
My solent to B ~~~~~ // this is code void solve() { ll n,p1,p2,q1,q2; cin>>n; cin>>p1>>p2>>q1>>q2; ll m1=(p1-q1)*(p1-q1); ll m2=(p2-q2)*(p2-q2); vector a(n); ll k=0; ll kk=0; for(auto &it:a){ cin>>it; k+=it; kk=max(kk,it); } ll l=max(0ll,2 * kk — k); if(k*k>=m1+m2&&m1+m2>=l*l)cout<<"YES"<<'\n'; else cout<<"NO"<<'\n'; } ~~~~~
How to do C ?
if n is odd, take all the values as l itself as xor of odd nos of l will give l and & will give l as well. also the highest set but of l and r must be diff or incase of n being even, xor of values will defn not have the highest bit set whereas it will in the & of the values. if n is even take first n-2 values as l and rest as the power of 2 greater than l
Consider two cases:
when n is odd, then if you put all l values in the array, your second condition will be always true, and it's also lexicographically smallest.
When n is even, then first find the minimum number x, such that x&l == 0.
-> Here you should make sure this x <= r and now you will just put l from 1 to n-2th and for n-1 and n-2 position put this x.
-> Take care of when n is 2, in that case answer will be -1
I was making the mistake of constructing it as half and half instead of n-2 and 2 :(. Realized the mistake at the very end and couldn't make change and submit in time. Nonetheless fun contest. In my mind I almost solved 3 so I'll take that as a win.
Initially I was also thinking the same. With practice, you will improve.
I did case work.. if n is odd.. you can just do
l l l l... n timesbut for even .. you will always have
andvalue zero because if you have 1 bit inandthen all bits have to be1.but thenxorfor that bit will be zero .. because of even count of 1sso we have to make
andvalue zero so MSB can't be same. so we have to look for next power of 2 afterlcalledp.. and then you can makel l l . .. p pand n=2 has no solution ... also ifp > rno solution[Deleted]
If n is odd, we can clearly see that, if we choose a[1] = a[2] = ... = a[n]:
a[1] & a[2] & .. & a[n] = a[1] xor a[2] xor ... xor a[n] (since a[1] xor a[2] = 0, a[3] xor a[4] = 0, ... a[n-2] xor a[n-1] = 0, giving us with 0 xor a[n] = a[n])
So clearly, the lexicographically smallest would be a[1] = a[2] = ... = a[n] = l.
If n is even, then there are 2 cases:
There does not exist 2 positive integers x and y with x xor y = x and y
Because if x & y contains a bit that is 1, the corresponding xor bit would be 0 and vice versa (there is only 1 exception, that is the bits are 0, but then, x and y would be 0, contradicting to the fact that x and y are positive integers)
The most straightforward way is that a[1] & a[2] & ... & a[n] = a[1] xor a[2] xor ... xor a[n] = 0.
For the array to be lexicographically smallest possible, the array should be in the form:
[a,a,a,a,...,a,b,b] where a is L and b is the smallest number such that L & b = 0. b can be found in O(log n). We can see that L <= b <= R, so if b > R, print out -1.
Now we only have to manipulate the position k. If k+1 >= n then print out b (a[n-1] and a[n] should be b) else print out L
consider parity of n
if odd we can just put l n times, because xor = l and and = l if even we can put l n-2 times, and something entirely disjoint from l 2 times, it turns out the smallest number that's entirely disjoint from l is 2^(msb(l)+1) as all previous bits, including msb(l) will be off. Because its disjoint the ands cancel out as well as all the xors, we result with 0 and 0 for and and xor.
Do I just suck at geometry or is C actually easier than B (I think both lol)
c is actually easier than b
C is much easier than B
Not for me, I solved B in 10 min and took 45 min for C :(
I won't register for chinese round any more :(
E is cool, but I like D very much. Also, this feels like a div 1 round lol
hey man, just asking, can a pupil (~1300) solve D? because i saw someone submit that
Maybe this contest is one of his/her first competitions. That is to say, his/her rating is lower than his/her real ability.
Once again on CF: terrible problem selection and round coordination. I had a chance to try problems from A to D. All of them are just pure math, no programming at all. From A to C it's just about handling edge cases, problem D I couldn't solve, but seems to be combinatorics. Authors, next time please consider giving it to math contest instead of programming competitions.
When I solved div2C my rank on the standing table was around 700 to 800.. but even when only 900 people have solved div2D, I thought my rank would be around 900 to 1000 because I didn't make any wrong submissions..
But my rank at the end is nearly > 1400 ... how can it fall so much when there are not too many AC for div2D
mostly because of point's system like me and many friends of mine solved C first then they go for B,so since one who had solved c at 15th minute and B at 30th minute and you had solved c at 25th minute and b at 15th minute chances can be a guy who had solved c at 15 minute will ranked higher for more information refer this blog
you can see this blog
oh I see, thanks so much for this explanation
another trash round :/
At least we didn't get pupils or newbies on top 20 (that's a good thing, right?)
950th rank and 6,000th rank solved the same amount of problems.
So the difference between Pupil and Candidate Master is how fast you figure out the little xor & trick.
Didn't really enjoy the problems, maybe that's skill issue on my end :)
It's true that mathematics is crucial for algorithm competitions, but aren't you taking this mathematics thing a bit too far?
This round (A-C) was more about edge cases than programming, I personally didn't enjoy it.
D, very good problem, I love it
E, shit, if it's put on C then >1000 people can solve it. Ai is only used in a process of *800 difficulty, just brute force Onlog^2n dp without any thinking can pass it
please give idea of D solution, thanks.
let f[i][j] be (i~n) choose j token to take
then in i-th place:
don't take that token. f[i][j]=f[i+1][j]
take it. there are (n-i-j+1) places to put that token. when you have the position i then the a[i] can be 1~i so f[i][j+1]=f[i+1][j]*(n-i-j+1)*i
then the final answer is f[0][0]+..+f[0][n]
ok thank you
Nice explanation. I was very close, and I loved it
What do you mean by "there are (n — i — j + 1) places to put that token"? I think that if i = 1 and j = 0, we can only place it in one spot—so why are you multiplying by n?
Also, I understand that a[i] can be between 1 and i, but doesn't it matter where I place it? Why are you multiplying directly by i?
i=1 and j=0 means you didn't let any i in 2-n to be already paired so that all i in 1-n can be paired with token 1, it's of n-i-j+1 choices. n-i is i+1 to n, j is the places already being paired, +1 is i itself
Because no matter which number you write in ai it has this certain way to pair so it means there are i ways this certain way to contribute to the final answer That's like for each pairing ways I calculate the number of corresponding a[] and get the sum, so one a[] can be calculated many times
Thanks for your explanation! Could you explain why a[i] must be positive when taking the i-th token?
I solved D but E felt to me much more difficult (just at first glance), what is your solution to it please ?
I suppose the *800 part is let p_i be A_i bitwise OR A_i-1, and then the problem has nothing else to do with A_i afterwards.
is it a norm now that B should be the trickiest problem of the contest
yeah, I figured C easily than B.
Just another trash round.
Nice problems! Enjoyed D specially. contest was more about math but :(
EdgecaseForces Round
I am getting atleast -200 lmao
is B pure math or am i missing any observations?
triangle inequality for me
You can always choose a direction that reduces the distance to however much you want for example you are at $$$(0, 0)$$$ and want to go to $$$(5, 0)$$$, $$$a = [3, 4]$$$, you can always use your first move to go to a point having where the distance between it and $$$(5, 0)$$$ is $$$4$$$, so as long as the distance doesn't exceed the sum of $$$a$$$ there always a solution
unless there is a number in $$$a$$$ larger than the rest, this will make the minimum distance you can move $$$2 * max - sum$$$
What's the idea for D
Reverse the problem. Don't ask which token can I place at a_i, but where can each token go. Token i can only go to some place >= i. Then, think about how many of those places might already be occupied.
they are multplying by all positions ahead of i that are not zero, but does not it depend on what the number on those positions was used, maybe that pos has a number which does not allow it to pick up till this location
I don't know what you mean by "they". What I did was make a dp of length n and dp[i] representing ways when i tokens have been removed. Now for each token j, I know if i tokens are removed j is the I+1st token removed and the available space for this jth token is (n-j)-i as exactly i of the places after j should be occupied.
WHY DO I SUCK AT THIS
I would really like to know what those who say before the competition ((( as a tester it is a very good competition ))) really do? div3 has become very easy div2 has become very difficult and question B is becoming more unsolvable The questions are all mathematical and it has been centuries since a question about graph has come up
I demand the removal of the law that reduces question scores over time.
I demand the removal of the law that reduces question scores when i get WA on test n (n > 1)
Today's contest was exceptionally hard for me. After spending 50 minutes on D, I instinctively knew that I was not going to solve it today. Will look into the editorial afterwards.
why the hell was D harder than most ~2400 problems for me
agree lol
checking back after upsolving E, it's easier than D IF you're a god at implementation (which i am not)
i definitely did not spend 2 hours implementing the solution...
seriously though E feels easier to imagine, while D is super abstract for me
Misread problem D and solved to find distinct removal configurations.
Same it's just nPi right?
I had fear of C now I have fear of B :)
I think D is about *2400
can 900 people solve 2400?
AI epoch, bro. Surely can :(
noooooo!!!!
What prompts do they use lol ?
Does anyone see that bond_at_codeforces (top 34 on the rankings) is an alien / cheater? 26 seconds between submission of prob A and prob B is insane
Also, how does this guy do 4 problems in under 3 minutes??
I didn't noticed the "lexicographically smallest" part of the C and kept wondering for 20 mins about the uniqueness of the solution .
B>C
what is the problem with my code? in test case 2 it says wrong but locally i get the right ans.
}
cout << 0 << endl; please
If the current value of a is even then you can perform both operations to get an increment of 1 (Lowest order bit is 0 so XOR_ing with 1 is same as +1) so the loop should look like :
There is a logical mistake as well since you cannot use the XOR operation to increment for Odd number and hence you perform +1 operation when current value is odd At which point you entire logic (for a<b branch) could be reduced to :
You mistakenly added x during the XOR operation and y during the addition operation.
im so noob thanks
Screencast with commentary
When is editorial coming out?
w name
E is too hard
performance was somewhat subpar but the music was awesome :D
I solved A and C but have absolutely no idea about B (Maths especially Geometry is really weak). Nothing. Can someone please provide me a hint by hint solution for it, it will be really helpful. Thanks !!
Up Up
Here you go
Try to think about a range of distances that you can reach from p, is q lies in this range?
You can construct a path from p to q if the sum of distances given >= the distance between p and q
Minimum distance you can reach using the given array is maximum a[i] — sum of all other a[i] but if this is negative you can adjust the path to make it equal 0.
There are 2 cases.distance to target is too far, or distance to target is too close.
Too far is easy, too close is the triangle inequality
hi
Let $$$P_1$$$ be the first point and $$$P_2$$$ be the second.
Can we reduce the case where $$$x_1 \ne x_2, y_1 \ne y_2$$$ (i.e. $$$P_1 \ne P_2$$$) to a case where they are equal?
Yes, we can treat the distance between $$$P_1$$$ and $$$P_2$$$ as its own separate value in $$$a$$$. Convince yourself that this problem is similar.
Are there any nice ways to create the answer if $$$P_1 = P_2$$$?
Yes. If $$$a=[3,4,5]$$$, we can imagine a $$$3-4-5$$$ right triangle being formed with one of the vertices being $$$P_1$$$. If $$$a=[2,2,2,2]$$$, then we can imagine a square. If $$$a=[3,3]$$$, then we can imagine a line going back and forth. If $$$a=[2,3,5]$$$, we can again imagine a line, this time going $$$5$$$ units to the right and $$$2+3=5$$$ units to the left.
It seems that it's possible as long as it's one of two different constructions:
Convince yourself that this actually does make sense.
How do we use hint 1 and 2 together? Create the new array of moves where $$$P_1 = P_2$$$, then find if we can create a non-degenerate polygon or a line that goes back and forth.
Think of it as this: let's say we drew first the longest edge. Then, since it is a non-degenerate polygon, this implies that the other edges must be at least the length of the longest edge. If it were less than, its not enough to cross the gap between the max length in the first place. If it were equal, then it's a line (which is actually our other case!).
In symbols, $$$\Sigma (a_i) - \max(a_i) \gt \max(a_i)$$$. The right side is the max edge, the left side is everything else.
Additionally, you need to use extra math in order to not use square roots (because floating point numbers are bad). I'll leave that up to you to figure out. Good luck!
you could actually do general polygon inequality (that is max size is less than sum of everything else) by adding another side length from p to q because then no matter what it is always a closed polygon.
Let's define the point $$$P$$$ as $$$P(p_x, p_y)$$$.
If you can reach a point $$$A$$$ whose distance from $$$P$$$ is equal to $$$d$$$ after completing $$$n$$$ moves, then you can reach any point whose distance from the point $$$P$$$ is $$$d$$$. Can you prove this?
That's because you can freely rotate the path from $$$P$$$ to $$$A$$$ around $$$P$$$ without violating the problem's conditions.
Let's say $$$l$$$ is the minimum possible distance from $$$P$$$, and $$$h$$$ is the maximum distance from $$$P$$$. Assume you can reach any point that satisfies $$$l \le d \le h$$$, where $$$d$$$ is the distance from $$$P$$$. Then consider you make a move of distance $$$a_i$$$ from those points. What would be the new values of $$$l$$$ and $$$h$$$?
Let's call the new values $$$l^\prime$$$ and $$$h^\prime$$$.
It's not too hard to prove this by drawing circles for several cases. It's also possible to prove you can reach any point whose distance from $$$P$$$ is equal to $$$d^\prime$$$ such that $$$l^\prime \le d^\prime \le h^\prime$$$.
The rest is not too hard. Start with $$$l = h = 0$$$, update them with each $$$a_i$$$, and check if $$$l \le \sqrt{(q_x - p_x)^2 + (q_y - p_y)^2} \le h$$$ holds for the final $$$l$$$ and $$$h$$$. To check this inequality precisely, you can compare squared values instead.
editorial ?
When will rating change will take place???
Math mains: A, B, and C are trivial! Everyone else: This contest was trash
Anyways, A: its just +1 but look for A = B+1 and odd edge case B: look for distances edge case and triangle inequality C: odds and evens and just replace 1s with 0s for even N
Someone streamed solutions here during contest https://www.youtube.com/live/kgB5w4AxdFk?si=kGOMS9BQXLKaYYIV
Here as well
Kindly consider these during plag check
solved B but I have a feeling my solution is incorrect, consider this test case:
shouldn't this be YES? rotate the first 2 segments by x where 4cos(x)=3?
edit: nvm i do get YES, i was running the wrong code lol
It's YES
I have some questions about problem B when calculate the mindist. Why just when maximum * 2 < sum, mindist will be 0. I try to solve it by DP, but it was hard for me.
Hello Everyone,
Is it due to rounding errors while calculating square root in Problem B that the approach doesn't work ?
Although I learned to never use sqrt on mathematical questions :))
Nah I used square root and I was just fine
I anyone is also pissed off by B and waiting for the editorial, here's the thing.
Idea: if it's possible to build the polygon with N+1 sides
[a1, ... , an, d], whered = dist(x, y), thenYES,NOotherwise.Condition — there's no a single side which exceeds the length of all the others (kinda same thing as for possible triangle check).
Implementing straightaway d=sqrt() didn't seem to work (IMO due to precision issues), so
D = d * d,s = sum(a[i]),S = s * sS < Dmx = max(a[i]),MX = mx * mx,r, = s - mx,R = r * rmx > r + d-->mx - r > d-->(mx - r)^2 > D-->MX + R - 2*mx*r > Dmx - r > d-->(mx - r)^2 > Dmx - r > d</-(mx - r)^2 > DThe second might be true but, at the same time, the first might not be true.
If our goal/desire/designation is to check
mx - r > dwe might choose to use from abundance of information of a particular situation, in particular, thatd > 0. So ifmx - r > dto happen -->mx - r > 0must happen.mx - r > d<--> (mx - r > 0and(mx - r)^2 > D)Statements are interchangeable (in this universe).
In more general case, that is with less information which force us to operate in general terms, there is this:
a > b<--> (a > 0andb > 0anda^2 > b^2ora < 0andb < 0anda^2 < b^2ora > 0andb < 0).// ImPoSe TaRiFfs hoooooGE
My solution for D.Token Removing with modulus functions defined in my template gives time limit exceeded
327642840
but replacing them with normal modulus operations it get accepted
327643413
is the time limit too strict or am i missing something (like modulo operations time complexity when modulus is non-prime)?
pls suggest me most efficient way to perform modulo operations
whoa!! I am awake next morning to upsolve D.. but no editorial.. please update
Well I'm quite a new competitor.Who could teach me how to read tutorial?
you are using words like
quiteandcould.. then you have good english .. so you can read the english part...but because editorial on codeforces are short.. it is difficult to understand the full logic sometimes...
if it is a recent contest I generally comment on the contest announcement or editoral post and ask people to help me understand it ..
or if it is a an old question .. I try to paste the editorial to chatgpt and ask it to explain it to me.
It was a nightmare..!
CutieSmileHaruka, why no editorial yet?
How to E?
You can try reading my solution to Problem E. https://codeforces.me/blog/entry/144489
The key insight after the transformation is that "at most one '0' can be flipped to '1'", and we incorporate this flipped bit into the DP state.
Nice music
a very good solution of the contest: solution for F
May I ask when would the tutorial be released
It is released now
Auto comment: topic has been updated by CutieSmileHaruka (previous revision, new revision, compare).
Auto comment: topic has been updated by CutieSmileHaruka (previous revision, new revision, compare).
Problem D and E is too hard.
Dear Codeforces team,
I would like to sincerely apologize for the situation regarding my submission for problem 2119D (submission ID: 327573902).
During the contest, I was physically present with my friend. We were solving the problems side by side, and I did not realize that this kind of collaboration, even without any intention to cheat, is considered a serious violation of Codeforces rules.
I now fully understand that any similarity between submissions — intentional or not — is not allowed, and I take full responsibility for this misunderstanding. I assure you this will not happen again, and I will be much more careful to follow all contest rules strictly in the future.
I kindly ask for leniency and hope you will consider this an unintentional first-time mistake.
Thank you for your understanding and for maintaining the integrity of the platform.
Best regards, [Artinzer0]
Hello Codeforces team,
I received a plagiarism warning for my solution 327591317 to problem 2119D, allegedly matching user GOW1455. I want to sincerely clarify that I did not cheat or share my code with anyone. I wrote the solution independently using VSCode on my personal computer.My VSCode proof
I later found out that the other user is from my college, but I don’t know them personally and had no interaction with them during or before the contest. I did not use any public IDEs (like Ideone), did not screen-share, and did not post my code anywhere.
I understand that unintentional similarities can occur, especially among students with similar backgrounds or problem-solving strategies. However, I assure you I participated honestly, and any similarity is purely coincidental.
I kindly request a manual review of my submission. I am also open to providing any additional information if required. Thank you for your time and understanding.
Best regards, ShaikJameelUrRahaman.
@MikeMirzayanov Could you please take a look at my appeal above? I’ve explained the situation in good faith and would really appreciate a manual review of my submission. Thank you!
Hello,
My solution to Problem A 327536304 was recently skipped due to alleged similarity with other submissions. I would like to clarify that I used Dijkstra's algorithm purely because the constraints were very small (n ≤ 100), and I couldn’t come up with the intended solution in the first couple of minutes, as I usually do for Div 2A problems. The approach worked within the limits, so I went ahead with it.
I’ve looked at some of the other flagged solutions, and the only commonality is the use of Dijkstra's algorithm, a well-known and standard technique. There’s no unusual similarity in code structure or implementation details beyond that.
I've been participating in contests regularly for months, and I would never consider cheating on a Div 2A problem. This contest was particularly meaningful to me, as it pushed me to Candidate Master for the first time.
I respectfully request that you review my submission again and lift the skipped status.
Thank you.
Hi Codeforces Team,
My submission 327537417 for problem 2119A was flagged due to similarity with others. I submitted the same logic earlier on CodeChef (ID: 1165443773, submitted ~1 month ago). The problems were different, but the approach overlapped naturally. I wrote and adapted it privately using my own code, no sharing or public paste sites.
Here’s the CodeChef link for reference: https://www.codechef.com/viewsolution/1165443773
Thank you for reviewing this. I’m happy to provide more details if needed.