你好，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).
user:Yujihae well i submiited same code which got wrong before 4 times doing just minimal changes and it got skipped bro...what is this ,it is just ruining someone's hardwork.
[user:Yujiahe]please look upon to my issue i resubmiited just same code doing minimal changes 4 times on 5th time it got skipped although it was giving wrong answers on first test case.later on i again submitted it,it didn't get skipped.finally i just want to say i am not a cheater if i have to cheat i would not have submitted solution after 50mins which is wrong on first test case.please review this issue and provide an explanation for this
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?
its a reference to a meme
hank do not abbreviate cyberpunk hank
thank god someone got the reference
you'll grow if you solve problems by yourself and not copy paste them to increase the solved problem count. you solved like 9 problems in a minute lol
yes, you shouldn't be nice to people here, the conventional rules of human society doesn't imply here.
ji verma ji
True man, recently I saw a blog on dp and it was really helpful for me, so I left a thanks to the author in the comments. Guess what? I got 10 downvotes. So people are being jealous that someone is being nice to another in this platform.
:)
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
Eveyone starts their programming journey from being a newbie to someone who's better than his previous self. keep solving and practicing
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
Why do you care? You're using ai anyway.
OMG!! Chinese round
Thanks for the contest!!!
Hope problems will be anti-AI , rather than similar to those in 1033....
1034 were pretty good tho
The pros and cons always work on a odd way...
As an author, I hope all the contestants GL & HF!
try to recover from last contest
wtf is FeOI and WAOI
it's a group in Luogu
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?
to promote: raise (someone) to a higher position or rank. ex: "she was promoted to General Manager".
So in that case We'd say "He promoted himself"
I think this contest will be full of math.
Bro ,sus
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://mirror.codeforces.com/blog/entry/131746
so surely i should start solving from D 🧐
haha nice!!! respect.
As a tester,I think this contest is really interesting.
Hope to see an easy contest
GreedyCoder234 is a cheater. Report her
How you know her gender $$$?$$$
Hoping I could perform at my potential this time :P
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
I think this contest is really interesting.
Excited
This contest is so orz that I have to compete. Hoping for a positive delta—I'm tired of catching up with my bro.
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
you have to violate twice to be disabled. and once its disabled it's gone forever.
you mean my old account is disabled forever?
yea maybe stop cheating man
I wish success to all participants... My friends, you are legends.
Thanks for you bro...
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.
Is testing still going on
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+)
good luck !
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?
What i dont understand is, in this dp, how are we able to prevent recounting ?
this is the part i dont understand:
So wont there be a case that: if you removed q-1 tokens in i-1 turns, then you Might have removed the kth token already?
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.
if number of terms are odd then all elements in the array will be equal and since we have to find lexicographical minimum all elements will equal to l now if no of terms are even then all elements can't be equal since it will make & value non zero so what you have to do is take one number x such that l&x=0 and replace last two elements will be x and first n-2 elements will be l and if x>r then no else yes this can't be done for n=2 so when n=2 ans is no
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 :(
Authors have a good taste in music :)
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.
That guy literally has skipped contests :)
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?
Thanks man !
Just loved your explanation
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 :(
should have attend biweekly instead
1 word: Trash
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.
horrible contest
Going to get my first negative, TwT. I hate Bit!
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 ?
Good round! Enjoyed problems A-D. Especially loves that all of them are more mathematical + you can't solve them "by-AC" — as for me it's very good when problem demands proof of solution.
But, as for me, there is a much gap between C & D ( 7340 & 980 ). As for me it's not very good and for people around 1400-1800 it will be better be one more problem between them.
Anyway, great round!
I got stuck on C :(
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
nah it happens , these BIT manipulation based problems are really difficult to debug.
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
The worst way to get closer to the point is to go on the opposite direction. If a move is the highest one, and it is more than the distance, you can go at most on the opposite direction, and then you have to go back straight with all the other moves. So each move should be less or equal than the sum of the other moves + the distance between the two points. If a move is less than or equal than the sum of the others + the distance, there are infinite ways to combine the moves to get to the final point
its just triangle inequality but generalized for any N-sided figure
I checked your code and I am doing the absolutely same thing, still I am getting WA. Can you help me out by checking my code once. Submission Link: https://mirror.codeforces.com/contest/2119/submission/327714561
No issues, got it. I was still using squared integers but they are not the same as rationals. The inequality takes a different form in my case. Using floating point numbers work. Thank You!!
no problem
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.
My Solution got accepted. Thank you everyone, reading all the different approaches and hints definitely helped build the thinking required for such problems. One major issue I was facing was treating squared distances the same way as normal ones, but I was wrong:
Polygon inequality is not true if all distances are squared, a1^2 + a2^2 + ... + an^2 + Correction Term >= 4*distPQ*distPQ -> Is True a1^2 + a2^2 + ... + an^2 > 2*distPQ*distPQ -> Not necessarily true due to the missing correction term.
The floating point numbers work but yes I also don`t have the habit of using floating points so not sure if a solution with them is good or not. Thank you others who have provided solutions without floating points.
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
that was my first contest ever, and daamn I was STUCK af
YuJiahe well i submiited same code which got wrong before 4 times doing just minimal changes and it got skipped bro...what is this ,it is just ruining someone's hardwork.
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.
user:Yujihae well i submiited same code which got wrong before 4 times doing just minimal changes and it got skipped bro...what is this ,it is just ruining someone's hardwork.
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
it does work with sqrt but it seems like what we need to consider is that it might be not a polygon in a strict sense (two-dimensional shape formed by connecting three or more line segments (sides) end-to-end), this could be just a line and in this case a1 + a2 + a3 +..+aN-1 could be equal to aN wherease in polygon case it must > aN for all sides(only then you can build a polygon). This tripped me up during contest as i considered only the condition with > and not =.
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
Enjoyed it
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..!
help me <3
CutieSmileHaruka, why no editorial yet?
How to E?
You can try reading my solution to Problem E. https://mirror.codeforces.com/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
Editorial ?
May I ask when would the tutorial be released
It is released now
I am unable debug why it showing WA-6 327713353
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.
I cannot see other people's code in the open hack stage of div3, and it shows N/A. How can I solve this problem? Is it a blind hack? In addition, I successfully became a green name after two div2 games, but now I still cannot see other people's solutions. How can I solve this problem? Or what specific requirements must be met to be allowed to see the code? Do I need to participate in a certain number of games or reach a certain rating?
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!
Username: Sachin250902 Submission ID: 327611833
I just received a message that my solution for problem 2119C coincides with other users. I want to clarify that I did not share my code with anyone, nor did I copy it from someone. I have no idea how others got similar code.
I might have written a common or simple solution that others also used, or it's possible my code was copied without my knowledge. I did not upload it to any public site or share it intentionally.
I kindly request you to reconsider the situation. I accept the rules and will make sure this doesn’t happen again. Thank you for your time
Hello Codeforces team,
I sincerely apologize for my actions during Round 1035.
During the contest, I watched a livestream on YouTube and ended up using part of the solution shown there in my submission. I now realize that this was a clear violation of the contest rules, and I take full responsibility for my mistake.
At the time, I underestimated how serious this was. I now fully understand the importance of fair competition and the integrity of this platform.
Please consider this my honest apology. I promise that this will never happen again. I truly want to learn and improve through Codeforces, and I hope to be given another chance to participate fairly.
Thank you for your understanding.
Best regards,
kytrieu
Hey Codeforces team,
I got a warning on my submission 327620327 for problem 2119C, and I just wanted to say that I wrote the code completely on my own. I didn’t copy or share it with anyone, and I’m honestly surprised it turned out similar to others — it must’ve been a coincidence.
I’ve been putting a lot of effort into learning and improving through these contests, and I’ve always tried to follow the rules. It would really mean a lot if you could take another look at it.
I know I still have a long way to go, but I genuinely want to grow in the right way. Please don’t let this one misunderstanding affect the hard work I’ve been doing.
Thanks for your time and understanding. (PranshuSharma357)
Subject: Request for Re-evaluation of Plagiarism Flag – Submission ID 327579970 for the problem 2119B and Submission ID 327582445 for the problem 2119C Dear Codeforces Team,
I’m writing to address a plagiarism notification I received regarding my submission (ID: 327579970) for Problem 2119B and my submission (ID: 327582445) for Problem 2119C. It has been flagged for matching with another user's solution. and I would like to firmly state that I worked on the problem independently without any external assistance.
I wrote my solution in VSCode on my personal machine, and at no point did I share my code, use any online IDEs, or make my work publicly accessible. I also did not communicate or collaborate with any other participant during the contest.
I understand that coincidences in logic or structure can sometimes occur, especially when many participants arrive at similar approaches to solve a problem. That said, I want to emphasize that my work was done with complete integrity.
vs code proof https://drive.google.com/file/d/1zOIuiPii-byAZJ9Qkant6ORZZgYdVYzP/view?usp=sharing https://drive.google.com/file/d/1tevAi3hpCEN1o_6ckvdg2dCNqdS3lIwv/view?usp=sharing
I’m more than willing to provide screenshots, logs, or any other proof needed to support my case. I accept the rules and make sure that this does not happens again
Thank you for your time and attention.
Sincerely,
Hey Codeforces team,
I received a message today that my solution 327601871 for the problem 2119C, coincides with other's solutions. I have not shared my code with anyone. I have explained my solution in details in this submission, how i approached it (328534134).
I do not have online compiler history but I can prove that i have not violated any rules. In just previous problem, i submitted wrong solution 3 times, because of pow() function instead of doing x*x. Also, it took me nearly one hour for me to solve a 1500 ratings problem (B at 20:38 and C at 21:24), which should not been taken if i was cheating.
I only have these Circumstantial evidence to prove my innocence. If, I have unintentionally submitted a very common looking solution, I sincerely apologize. But I would like to say that it took me 1 year and 400+ LC problem to reach pupil at CF, if i wanted to cheat i would have achieved it under 40 problems.
Please team Codeforces, take a look at it.
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.
Hello Codeforces team,
I have received the notification that my solution for Problem 2119A coincided with other submissions in this round.
I want to clarify that I did not intentionally share my code with anyone, nor did I copy it from anyone else. I understand that my solution matching others so closely may still be considered a violation of the rules.
I fully respect the rules of fair competition, and I apologize for any inconvenience caused. I will make sure to be more careful in the future to avoid any similar issues.
Thank you for your understanding and for your hard work organizing these contests.
Hi, I'm appealing the flag on solution 327610026 (problem 2119C). I regularly use Ideone without knowing that the default setting makes code public, which unintentionally allowed others to see and copy it.I can also provide with the logic of my code .I didn’t share links or collaborate—I simply didn't realize I needed to manually switch it to private. Today after getting an alert, i realised about this feature... I sincerely apologize for the unintentional leak. This was not deliberate plagiarism. i wont repeat this mistake next contest.
Dear Codeforces Team,
I recently received a plagiarism notification regarding my submission 327600525 for Problem 2119D. The report mentions that my code significantly coincides with several other submissions. I want to clarify that I am genuinely surprised and distressed by this notification, as I have neither shared my code with anyone nor copied from any external source during or after the contest.
I wrote the solution entirely on my own during the contest. I did not use any online collaboration tools, public IDEs, or code-sharing platforms like Ideone, Pastebin, GitHub, etc., in public mode. I also did not communicate or collaborate with anyone during the contest. I have taken every possible step to protect the integrity of my submission.
I understand that Codeforces uses robust tools to detect similarities, and I respect the platform's efforts to maintain fairness. However, in this case, I kindly request a re-evaluation of the context of my submission. I have no idea how my solution ended up resembling so many others, and I can only assume that perhaps a common implementation strategy, standard algorithm, or widespread idea led to this overlap.
As someone who values the learning and challenge aspect of competitive programming, I have always strived to follow the rules sincerely. This incident has left me quite disheartened, but I am fully willing to cooperate if further clarification or proof is required from my side.
I respectfully request that you consider my explanation and intent, and I sincerely hope for a fair and just review.
Thank you for your time and the effort you put into keeping Codeforces fair for all.
Subject: Clarification on Submission 327600945 (Problem 2119A)
Hello, I received a plagiarism warning for my submission 327600945 for Problem A (Add or XOR) from Round 1035. I want to clarify that I wrote the code completely on my own using a standard Dijkstra-based approach, modeling each value as a node in a graph and using weighted edges for the two operations. I did not copy from anyone, and I did not share my code. I also did not use any public IDE like Ideone or Replit during the contest. This is my first time encountering such an issue, and I take the rules very seriously. I kindly request you to review my case. Thank you for your time and consideration.
Hi, my solution for problem 2119C (submission 327613006) was flagged for plagiarism. I want to clarify that I wrote the code myself and did not copy from anyone. I do not know Herikpatel02 nor did I share my code with anyone. If there is any similarity, it may be due to a common algorithm or template. I request a review of the decision. 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.