Hi, Codeforces!
We are pleased to invite you to EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2), which will be held on Aug/11/2024 17:35 (Moscow time).
The problems are prepared by Flamire, le0n and xcyle. You will be given 8 problems and 3 hours to solve them. Two problems are divided into two subtasks. The round will be rated for everyone.
We would like to thank everyone who has helped prepare for this round:
- TheScrasse for his brilliant coordination.
- AdunAdunov and Alexdat2000 for Russian translation.
- zhoukangyang, arvindf232, MagicalFlower, rui_er, LipArcanjo, zhaohaikun, Mr_Wu, lambert0704, acniu, wenhao801, using233, Kaey, DeadlyCritic, _RedWine_, Bossusuprem, Hihihah, FetFot, MatteoArcari, Vamperox, songhongyi, AdunAdunov for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon.
The score distribution is 500 - 750 - 1000 - (1250 - 1250) - 2000 - (2000 - 1250) - 4000 - 6000
Good luck, have fun!
Congratulations to the winners:
UPD: Editorial is out!
And now, a few words from today's sponsor!
About EPIC Institute of Technology
EPIC Institute of Technology is an innovative educational project, driven by the Deltix team under the EPAM Systems umbrella. As part of EPIC — EPAM Product Innovation Center, we aim to cultivate the brightest minds and prepare them for a future in cutting-edge technology projects.
Why EPIC:
EPIC Institute of Technology is an accelerator for the best talents. Our students will acquire hands-on experience in one of the selected major programs, all of which are highly demanded right now on top projects, together with the fundamental knowledge, so indispensable for real professionals. Successful graduates will have a unique chance to jumpstart their career on the most challenging and interesting EPAM projects worldwide. You will join the community of intelligent and driven individuals and have an honor to work with and learn from them.
Here are the answers to the most common questions:
How much does education cost?
EPIC Institute of Technology is completely free. There are no fees to register for exams, tuition fees or any other hidden liabilities. The only restriction for getting into EPIC Institute of Technology is age. You must be older than 18 years old to become a student.
How is the educational process organized?
Each program lasts exactly one year. The academic year consists of two semesters. Courses in the first semester are the same for all programs. Courses in the second semester depend on the selected major program.
During the semester, students complete homework assignments and take 2 exams—a midterm and a final. The final grade a student gets for each training course depends on the quality of completed assignments and participation in practical classes.
How will the classes be held?
Lectures will be pre-recorded and available for self-study. Practical classes will be held at the specified time according to the provided schedule. Also, students will have an access to a Discord server, where they can discuss topics of academic interest with teachers and other students.
In what language will I study?
All programs are in English.
How can I apply?
The admissions process is as follows:
Fill out the form on the website.
Take part in one of the entrance exams that will be held in our Codeforces group. You can also find past exam breakdowns there, which may help you in your preparation. Exam dates will be announced later, so stay tuned to the announcement channel and our LinkedIn group.
If you successfully pass the exam, you will receive an invitation email.
What will happen after graduation?
All EPIC Institute of Technology graduates will get a diploma and the best students will be offered to join, either as an intern or a full-time position, one of the hot EPAM projects where skills acquired at EPIC Institute of Technology will be demanded.
Please visit our website to learn more about EPIC Institute of Technology and the available programs. If you have any questions, you can quickly ask them in our chat.
I hope Gennady will win this round, break 4000, and finally achieve a new rank 'God'!
the only true gigachad of programming to bless the mortal world.
in his heaven we all will be a red coder :)
None of that will happen because the winner will be me
lol he didn't even register to this round
I am the first comment ;)
Then I'm 0th comment, lol
As a tester, I missed the opportunity to post the first comment because I spent too much time thinking about what to post as an "as a tester" comment.
yay! as a tester & translator, good luck to everyone!
$$${\color{orange}{\text{As}}}$$$ $$${\color{purple}{\text{a}}}$$$ $$${\color{blue}{\text{tester}}}$$$,
why did it get so many upvotes?
Why not
I got -155 last EPIC round, hopefully it will go better this time!
The last EPIC also went badly for me, I hope not to screw up problem C again ;)
that problem C was really weird
Welp... I think EPIC rounds are just cursed for you at this point lol
Welp, at least not an EPIC fail like last time!
As a tester, I tested this round.
As a tester, I suggest you taking a nap when you got stuck. (It did help me)
BTW le0n is so cute! It's such a pity we don't have a photo of the authors.
are they a cat person irl too?
Perhaps le0n is more like a cat irl.
Yes!
boooo 3-hour round
My last performance in EPIC div1+2 was so bad. Hope I can come back this round
Hope tourist cross 4000 rating after this round.
le0n is BeiJing's Captain!
Can anyone please explain the score distribution (esp the bracket part)?
The score distribution is 500 — 750 — 1000 — (1000 — 1000) — 2000 — (2000 — 1250) — 4000 — 6000
The brackets means the problems (in this case pD and pF) are divided into subtasks. So you'll see problem D1, D2 and F1, F2 in the competition.
Usually, the second part has tighter constraints, and a code passing the second part would also pass the first part (hence the harder second part might award less points, like in pF. But actually you get 2000+1250 by solving the hard and only 2000 by solving the easy.)
However there are examples where the two parts are different questions, such as problem 1984C1 and 1984C2.
I appreciate you telling me that in a comprehensive manner. Thank you BaoCoder613
Hoping to break the 1400 barrier and becoming specialist this contest! Wishing everyone goodluck!
all the best!!
good luck
How many problems you are targeting to solve?
please no median this time
Hopefully the problem score distribution is proportional to the problem difficulty this time.
Hopefully I can break 1600 barrier :)
Good luck, Gennady.
hope to reach expert in this round
All the best everyone
Did you notice that the logo in the announcement doesn't loop? This is the first time I saw a GIF not looping. Did some search and found out that there's a “loop count” field in a GIF file.
I hope the best for every candidate.
I hope I will become Red after this round
I hope I will become Red after this round
Am I a mad man by going in div1+2 and expect to reach specialist?
no, im mad for trying to reach expert
We're both mad man then, let's do it.
fr best of luck!
I'm ready to take my minus rating. Today problem got me real good but I'm convinced
Lack of sleep got me real good :)
All eyes on tourist!
He is not registered ;(
Situation is tensed in Belarus
maybe that's why
As a newbie, I am sure that I will lose my rating.
Today's Target :- A, B and C.
Let's hope it won't backfire horribly! Like on the last Div 2. Or on the last EPIC Div 2.
Today's objective: Survive
where is tourist :<<<
hope for Salah7_a
all the best
My brain ain't braining after seeing problem B and C.
Not intending to be whiny but 1100 ACs for D2 is crazy ngl (all evidence points towards cheaters). Someone remind me to skip the next EPIC round (got -117 delta lol).
I hope I am not the only one skipping both D1+D2 to solve E+F, like I honestly can't grasp how to implement even D1...
My implementation was really messy but the idea (at least for me) was to notice that the nodes in a perfect binary tree have to have specific positions. Like, 2 has to be either 1 after $$$1$$$ or $$$2^{k-1}$$$ after 1, and so on like that.
So I kept a Fenwick tree $$$c$$$ where $$$c_i$$$ represented whether node $$$i$$$ was in the right spot in reference to its parent.
Then after each query, I just checked if $$$\sum_{i=1}^n c_i = n$$$.
F*ck me, I was stupid. In fact if I got it right, that could be implemented much more simple even, not requiring a Fenwick tree.
Thank you.
I think I tried along these lines but couldn't convert to a right solution. Got WA at pretest 4. Can you help me with this pls?
Put it in spoiler
any suggest on C to deal with epsilon stuff in python?
You don't need to. Do not sqrt it, just compare the squares.
oh man... thanks. Too late to notice my naive-ness
*naivety.
In fact by removing hyphen,
naivenessis actually a word. Learn something new everyday, I guess.ah ha, good one
i did'nt undersatnd why it gives WA when we use sqrt((x2-x1)^2 + (y2-y1)^2))...
but it got accepted when i removed sqrt
Precision error. Especially so when comparation does account for equal values.
ohhhhhhhhh... i did'nt think 'bout it
thank's bro
For me A >> B :(
Please someone explain with proof...
I was able to come up with a logic on pen & paper but could not implement it :(
it took me an hour or even more to derive it mathematically and implement it :')
Just thought to break into rows and columns and then multiply both as it was given max(x,y) which indicated both were independent.
hope this helps
this is a bit over complicated
Solution is just
min(k, width)*min(k, heigth)basically you can make a k x k square of all different colors and just copy it around. But if one side of the board is smaller than k you can cut a part of the square that doesn't fit (either in height or width independently)
If N ≥ K and M ≥ K, then at least K×K colors are necessary, because we cannot repeat any color within any K×K square. This is also sufficient, because if we have decided on one K×K square with K×K distinct colors, we can simply tile the grid with copies of that square, which guarantees that cells with the same color have a distance of at least K. So in this case the answer is simply K^2.
When N < K or M < K, then we can still tile the grid, but we need fewer than K rows and/or columns, so the solution becomes simply min(N, K) × min(M, K).
EPIC fail
Couldn't solve C. The fact that I rarely got AC from a problem relating to real numbers :(.
Then don't do real numbers.
you don't need real numbers
kudos to your spirit tho, you tried till the end and got D1 :)
Actually I was about to give up after seeing thousands of people got accepted in C, before trying to ignore my despair about that and continue.
2.6k solves on that D1? lmao sure
are you forgetting that this is div1+2?
nop i am not, if you will take a quick look at people in the leaderboard , you will find a staggering lot CMs, IMs skipping D1,D2 and going for E. While there a HELL LOT and yeah i mean a LOTTT of pupils and specialists solving D1 who are not alt accounts, and guess whats the common factor? They started submitting D1 after 1:35 hr and then submitted D2 wihtin a span of 1-5 mins .
I'm not noticing much around 1:35 mark, but I will admit that D2 submissions are suspect. Plenty of newbies who were getting rank 10k+ in contests a few weeks ago suddenly solving it.
Yeah I even solved F1 but failed in solving D）
if you know basic segment tree or BIT ( Fenwick ), you can also solve it :) .
The constraint that it is complete binary tree, made the question very easy...
i mean i agree to that i dont know fenwicks :) , but 2.6k people with a lot of pupils and specialists like come on most of them dont know fenwick.
dude it's a div2c you think bit or fenwick is necessary?
well i am talking about D1, and go and look at people at rank 502 and 504 in the leaderboard and tell me they are not cheaters, lmao
sorry brainfarted, i meant d not c
even so div2d VERY rarely requires seg/fenwick, I solved D1 (but not D2) using just std::set and a bfs
brother you are missing my point :). My point is not about people who solved only D1 , or who solved D1 and D2 but like there is a gap of 20+ mins in their submission. I am talkng about pupils and specialists solving D1 and D2 within 5 minutes cuz they are pasting the same code in both, i.e. the code that is leaked is for D2 and works on D1. Like i literally opened a random page at rank 450+ and you will find lots of people like this.
Just examples from a 30 sec look , ranks: 502, 504, 510, 527 even if 2 of them are cheaters it took me 30 sec to identify them that means there a hell lot of them
don't worry, things take time. It is quite easy, you can learn it before system testing finishes !!
https://www.youtube.com/watch?v=CWDQJGaN1gY
Google for more resources.
thanks man
Definitely a lot of cheating going on.
Found this guy Aryanap963 in my room who looks suspicious with the biggest red flag being he's from IIT BHU
I have seen a lot of shitty very obvious cheaters from IIT KGP on this contest too. Like on one hand there is a demon like Dominater069 and then there are these cheaters from a same , and I believe prestigious college, I mean I even don't care that much about my rating but the thing is this mass cheating thing is just getting sader and sader :)
is D2 HLD ?
275842383
Hello, I'm wondering what is wrong on my code here. It fails on Test Case 4 and have been searching the error for more than an hour but don't find it.
Stuck at C for more than one hour before I realize it's simply to solve the intersection between perpendicular bisector and the path.
Me while submitting D2: "Yeah it's definitely gonna TLE"
OMG running on pretest 10 !!
OMG running on pretest 20 !!
TLE on pretest 23
WHY GIVE HOPE ?????
be thankful to organiser. It could have been worse.
OMG running on pretest 10 !!
OMG running on pretest 20 !!
OMG Pretest Passed !!
FST on test case 183 :(
Glass half-full half-empty brother. Think on positive side :) ,
E < D < C
LOL, kidding right ?
C is just taking distance of circle to target, and comparing if it is less than or equal to character's distance from target.
One simple if condition... The only thing is,,, we need to keep the square of the distance, rather than taking square-root.
E was waaaaay more intuitive for me than C.
In C I thought we shoud take colinear vector and for each point check if distance from intersection to circle center is less than distance to start point.
E has a simple stack solution (you can check my sub: 275826831)
Please don't make me feel further depressed lol
I solved C in 5 minutes but came up with all kinds of wrong intuitions on E so that I almost could not solve it. I literally debugged E for 1.5 hours using a random generator and completely wrote new solutions several times. The solution is simple but it was a hard way to reach there...
In a way, I can see their sentiment on E < C. E actually required less "thinking" to come up with the idea, like the solution is straight-up simulating the given process in a careful way — at least the catch is partially within what's given. For C, it's more covert.
I think the hard part is to convince yourself that this works and not the implementation difficulty...
My way of convincing is that if you can't go to the end point through a straight line and instead you bump into a circle, you can't go to the end point through a curve without bumping as well
sure? I got C in 15 minutes and struugled 2hours for D and ended up not solving it :/
nice problems but i'm too weak for them.
Was able to blaze trough ABC in half an hour but then i saw D. Got the idea on how to solve it quiet fast but then didn't manage to implement it in over 2h. Quite an EPIC fail Otherways great contest
can you tell me your thought process in B ?
Bob can only win if he manage to delete the same element which is deleted by Alice in each operation, and this is only possible when b == a or b == reverse(a).
Lets say that we have a = {1,2,3} and b = {2,3,1}. In this case if alice chooses to remove 3 bob will have to remove a number that is not 3, since his 3 is not on the edge of the array. Now alice can just remove everything except for what bob removed on his first move like this:
What we noticed is that bob will always want to remove the same number as alice since if he doesn't he looses. Knowing this bob will win if he at all points has the same numbers that he can remove as alice. So we will just check if a = b or if REVERSE(a) = b since in that case they still have the same options every turn.
Was writing line intersection in C for an hour(problems with precision), only to realise it is solved with one distance check.
kak?
jest' ya tupoy
true story, cost too much time on intersection for naught. I too, fall for the same trap
i was thinking the same kind of thing ... I just guessed the distance check at the end.. can you explain me the proof ?
Can't prove it. Just guessed it is something simple considering how many people solved it. Distance solution was kinda reasonable so I tried it.
I did some haphazard proof on pen and paper that first it's always optimal to take a straight line between start and end points. Then I started doing some perpendicular distance stuff and then I checked using Pythagoras theorem and found that if a circle will intersect the straight path at some time "t" before you reach that same point, then it will for sure also intersect the end point before you reach it. Hence you can just check if any circle reaches the end point before you do. Honestly it's kind of a half-assed thought process that I just went with intuitively so I didn't really have a formal proof.
Assume you walk the straight line from A to B. Then for each circle with origin C, you can calculate the earliest time a when the circle touches the line AB, which is just the closest point from AB to C:
At time c > a, the circle covers some length 2b of the segment:
The Pythagorean theorem says a² + b² = c², and a is constant, so if c grows at a rate of 1/s, then b must grow at a rate greater than 1/s, which means that even if you are ahead of the circle, it will eventually catch up to you, unless you reach the destination (B) before the circle does. That's why it suffices to check that the distance AB < distance BC for all circle origins C.
This also shows that there is no point in following a curved path (which seems plausible initially), because if distance AB < distance BC then you can just walk the straight path, and if distance AB ≥ distance BC you cannot reach B before the circle does, so there is no solution.
I fell for the same trap :/
Problem B really screwed up this contest for me lol
D2 — check if 2 neighbors could be next to each other ina a correct dfs order. Check it for every neighbors and update during swaps. Use lca to check if they could be next to each other
In D1, I checked if the children were initially OK for all elements and then only checked for the swapped elements and their parents. But this gives WA on pretest 3. Can anyone explain why?
Submission for reference
I had the same problem. I'm not sure if it's your problem, but you should check for OK for the children of the nodes swapped too. This is because their answers could have change.
Submission for reference
What I was doing wrong was running into the wrong memory location, and instead of giving a Runtime error, it just gave a WA :/
was there a chance I could get pretests passed with some more pragmas? it initially was tle10. with pragmas it got till pretest 13 https://mirror.codeforces.com/contest/2002/submission/275836926
I see a lot of complaints about C and even though I didn't get stuck on it, I agree it was misplaced. Geometry automatically adds difficulty, doesn't matter if there's a clever idea behind that simplifies it — a clever idea adds difficulty!
More than 8k people got AC though, so it's not really bad.
Most submitted without proving. Just so happens that the first naive check works because of a clever observation
3 hour contest and it's C. If you get stuck, you start guessing.
Is there anyone trying to find projections in problem C?
I did and failed in vain. Not handling the epsilon good enough
I did shortest distance between line and point then take the intersect to calculate distance between start point and compare distance.
and then realize that line equation doesn't worked for perpendicular line so I used Area of triangle then take height and use pythagorean theorem to calculate base and compare distance. which also fail
I started doing the perpendicular distance thing but then luckily I realized if a circle reaches that perpendicular distance point on the line before you (or any point on the line in fact), then it will for sure reach the end point before you as well (I did it using Pythagoras theorem and some inequality). So I scrapped everything and just checked distance from end point
I immediately thought of the Voronoi diagram. Makes intuition a whole lot easier.
D is nice, it made me notice how I don't know DFS.
The main idea for E is the same as https://uoj.ac/contest/91/problem/890 . I thought I should do something different because at least one of the testers should know it, sad...
how to solve D2?
1 and half hours of debugging C using double only to realize greedy argument with integer distance calculation without sqrt
Just checking distance from centre to destination is either completly braindead or ingenious. No in between. Guess it is one of those times when not proving is helpful.
I proved and solved in 3mins, it is possible
bro you are dominater
i guessed and solved in almost 50 mins, we are not the same
us
Quick proof for C.
Your speed and Circle speed is same. 1 unit per second. If circle reaches the target before you do, there is no way, you can reach the target. Try to do it for just one circle. and you will get it. :D
thanks for this proof failed to solve the problem but will do learn from it
I think this is only a proof that it is necessary, not that it is sufficient.
Completely got tricked in both B and C. Hands down to the problem setters for giving good problems and traps to test us. Thanks and appreciated.
how did you solve B?
Since the game is taking the 1st and last element, you can break it down into 2 options: - An array from a[1..x] - A reversed array of a[x+1..n] Bob want to match with Alice every turn so he can win. So you need to compare array b with a.
There's 4 option to compare just "if then" compare them all. And there's an edge case (n is odd, in my case I got RTE coz I tried to compare 2 array with different length)
if array A and B are same means Bob can always delete element alice deleted and get same ans it is also the case for when A is reverse of B , Bob can again do it . else Alice win
ooooh I overkilled the problem again. Oops that was dumb of me
That D (D1) was way harder than usual D in Div2
Was D2 just D1 with binary search and some advanced data structures or is there a unique solution?
D2 was about checking adjacent elements and seeing if they can exist as an adjacent element. I think either the problem order should have been D1,E (no D2) or E,D2 (no D1).
The scoring told you exactly that. You weren't able to add 1250 and 1250?
I once got jinxed because of relying on scoring to predict my problem solving order. So I don't really check scoring now.
Just a thought at 178th minute for F2, I think it was correct but couldn't confirm. Is it just F1 with more complex casework?
In F1 I thought of DPing the availability of states within range $$$[n-300, n]$$$, F2 would be the same but with more case-handling (checking $$$(i, j)$$$ with $$$i \in [n-300, n]$$$ and $$$j \in [m-300, m]$$$, cannot force $$$i \lt j$$$ like in F1 since $$$n$$$ and $$$m$$$ aren't symmetric anymore).
Is it me or someone else also getting "NO" response in 5th test case for C on my local compiler.
Test case 5: 1 999999998 1000000000 999999999 999999999 1 1
Happened to me and it was because I was using the built-in pow function instead of just multiplying which resulted in a overflow.
Thanks got it. That was the issue.
if you are using double then there would be some precision issues .. i jut squared the differences and used long long (didn't take root)
Was having issues with understanding pow fn. Resolved now. Thanks
use long double/powl instead of double/pow
Thanks. Got the issue now.
I think i can pass D2 now. Debug finished. Why not another 30 minutes XD
I just realised: Problems A-C all have a simple solution and a complex proof.
true dude
Problems C proof is two words : "Discrete continuity"
Can you elaborate?
The most wise thing I have ever done in this contest, is skip D2 and try E in the earliest time. Because I found D2 way much harder than E, at least for me.
And you motivated me to do the same.
somehow I solved B in 2 minutes but struggled lot in A
A round made up of problems with huge personal differences.
Can D1 be solved by calculating hashes for all unique dfs trees and answering yes on queries for which hash exists and no for those which doesnt?
I solve D1 via this method, but fail at D2 'cuz I have to update all ancestors, which can be $$$O(n)$$$. As of D1, the constraint ensures the depth is $$$O(\log n)$$$ so the complexity is $$$O(n\log^2n)$$$
I dont understand what you mean by updating all ancestor, cant we just re update the hash?
In my solution, I use a segment tree to maintain hashes, and for each query, the hashes of both query nodes and its ancesters need to be recalculated. What's your thought?
Thinking the same... I didn't understand how check the adjacent elements works... Someone please explain
any one who solved A in o(1) can explain how did he derive the equation ?
observed test cases and figured out the formula
min(n,k)*min(m,k).....
input: 5 1 10000
output: 5*1=5
D and E were really cool :)
Never has a task destroyed my confidence in my braincells as thouroughly as D1. How are people able to solve up to D2 so fast? Am I just a brainlet or is there some straightforward observation that I'm missing?
In problems of the form "swap/modify elements and say if the array is good", you usually have to break down the given global condition $$$C$$$ into local conditions $$$C = c_1 \land \ldots \land c_k$$$ such that each modification impacts a small number of local conditions, and each local condition can be verified quickly.
Then, you maintain for each condition if it's currently true or false, and the count of satisfied conditions.
I usually try to find a necessary set of conditions, and then alternate between simplifying/weakening the condition (to make it local) and strengthening the condition (to make it sufficient).
First attempt (transform the condition into a set of conditions). First I remark that when $$$p_i = u$$$, the interval $$$[p_{i+1}, \ldots, p_{i+\mathrm{sz}_u-1}]$$$ must be a DFS order of the subtree of $$$u$$$. It's necessary and sufficient, but not local (the condition $$$c_1$$$ is literally the global condition, we didn't make any progress).
So we would like to rewrite $$$c_u = \phi_u \land c_{v_1} \land \ldots \land c_{v_k}$$$ where $$$\phi_u$$$ is a brand new local condition around $$$u$$$ and $$$v_1 \ldots v_k$$$ the direct children. That way, we will have $$$C = \phi_1 \land \ldots \land \phi_n$$$ by induction.
It's very powerful because you can rely on strong $$$c_v$$$ while building $$$\phi_u$$$!
Second attempt (weaken the condition $$$c_u$$$ to make it local around $$$u$$$). All direct children of $$$u$$$ are in the interval $$$[pos_u + 1, pos_u + sz_u-1]$$$. It's necessary and local (when you swap two nodes $$$u$$$ and $$$v$$$, you update the good/bad status of $$$u, v$$$ and their parents), but not sufficient anymore, because a child of a child could be outside the interval.
Third attempt (strengthen the condition to be able to rely on induction). I ask $$$[pos_v, pos_v + sz_v - 1] \subset [pos_u +1, pos_u+sz_u-1]$$$, it's both necessary, sufficient (by induction) and still local. For example, you can use std::set to get $$$\min(pos_v)$$$ and $$$\max(pos_v + sz_v)$$$.
There is also a linear-time solution, check the editorial!
That's very neat! Thanks
We have a problem in which we want to find a sufficient and necessary conditions, so we just throw in necessary/sufficient conditions until AC (my real thought process)
Can someone explain logic for D1?
height of the tree cannot be greater than 15.
Now check the all the conditions like the distances of siblings should be constant with a certain value , positions of children should always be greater than parent and also one of the children should adjacent to the parent.
My solution — 275851102
P.S: I used a lot of map which resulted in TLE and after changing them into array, I cannot debug till the end of contest.
Thanks for geometry!!
when will be rating roll back??
any idea?
ey eyy finally rating roll back!!
How to solve problem H?
Be LGM!
A , B , C , D1 ... G problems be like
https://imgur.com/i6ntoTg
https://imgur.com/NEIbTcL
in problem B what if alice has 1 3 5 2 4 and bob has 4 3 5 2 1 how does alice win ?
alice 1 bob 1 alice 3 and bob sucks
Alice removes 4. If Bob removes 4, then Alice can remove 2 and Bob cannot remove 2. If he tries to remove 2 by removing 1, Alice can just keep 1.
If Bob removes 1, Alice can just keep 1.
My Insights for A,B,C
Observed that answer is $$$\min(n,k) \cdot \min(m,k)$$$ Total complexity is $$$\mathcal{O}(1)$$$
Since We're performing optimally we'll keep removing from left or right thus
Thus Bob can win only and only if $a$ is the same as $$$b$$$ or $$$a=b^{-1}$$$ i.e. $$$b$$$ reversed.
Total complexity is $$$\mathcal{O}(n)$$$
The $$$mindist$$$ that is possible is $$$\min_{i=1}^n \sqrt{x_i^2+y_i^2}$$$ overall points , and the distance needed to connect $$$(x_s,y_s)$$$ and $$$(x_t,y_t)$$$ is $$$\sqrt{(x_s-x_t)^2+(y_s-y_t)^2}$$$ , let's call it $$$d$$$ , we must have $$$\text{mindist} \le d$$$ so that it's possible to connect $$$(x_s,y_s)$$$ and $$$(x_t,y_t)$$$ without intersection of circles.
Don't use square root for avoiding square root errors , it's enough to store $$$(\Delta x)^2+(\Delta y)^2$$$
Total complexity is $$$\mathcal{O}(n)$$$
Solved D1 by hashing the set of nodes in the subtree of each node, and updating the paths for each query.
submission
seems very hackable though, is it feasible?
Hi, can someone please help me understand why this code doesn't work for D1? Thanks.
275855167
Still no one rainboy the problem H
My solution for D1 was to use a node's relative position to its parent. In a DFS of a perfect binary tree, a node can only be in 2 possible positions with respect to its parent node (Ex: for size 3, we can either have
1 2 3or1 3 2, i.e. 2 can only be at a distance 1 or 2 from node 1. Same for node 3). So I just maintained a set of "wrong" nodes that did not satisfy this condition. Whenever 2 nodes x and y are swapped, we just check if x and y are wrong nodes after the switch (I did this using a hashmap to maintain positions of parent nodes). Apart from this, you also have to check if the children of x and y are in the right positions with respect to their parents, as that relative position may have changed after swapping x and y. After a swap, if the set of wrong nodes is empty, then it's a valid DFS. However, this only works for D1 as the complexity increases with an increase in the number of children per node. Maybe some data structure could help but I couldn't think of it in the contest.i spent the contest brainrotting on this idea, it works because there's only two nodes per level and the subtree sizes of both children are the same
if you generalize the condition to this problem's description of a valid dfs order), you can do some subtree xor hashing thing, though i couldn't come up with any provable solution (ideally you would only need to add O(1) or O(log(n)) bad nodes to your set per swap)
here was my final solution 275822556 (it's definitely wrong btw but its hard to come up with random tests against it probably, i tried locally too). maybe there's some provable bound or a smarter way to maintain the bad nodes.
Thanks for sharing! Can you explain the hashing part? I don't think I quite understood it from the code. I didn't even consider hashing at all to solve something like this lol
so with xor hashing, you want to map every element to a random number (in my case i used two random numbers to make the hash bigger)
then, if you want to check if two sets of elements are the same, you can just instead take the total xor of their hashes
the valid DFS order check that I mentioned is the same as checking whether the set of nodes in my subtree is equal to the set of nodes in the range [position[x], position[x] + size_of_subtree[x]) of the dfs order, so you can verify that a DFS order works by checking the range hash on the dfs order for all nodes, which can be done with a segment tree (after subtree xor hashes)
to limit the amount of nodes we check, I have no idea how to do it properly with this approach, but I heuristic bashed by adding node X, the node before X in the dfs order, the parent of X, and then the parents of each of those as well
I enjoyed problem F very much! G, on the other hand, left me dissatisfied with the contest, because I feel like I just played the system and didn't solve it.
I have $$$O(N*Q)$$$ solution for D1. But I am curious about how any tester or author didn't notice that fact.
My submission: 275797240
UPD: Wrong submission, sorry fixed
There are some submissions to G that partition into equal halves, I wonder if it's possible to bound the time complexity or hack them:
what is causing run time error?
https://mirror.codeforces.com/contest/2002/submission/275844693
Nobody is going through that messy code just to debug runtime error!
Either I'm blind or there is no H in the editorial...
became pupil
I will reach expert today
Meanwhile problem D test case 3:
UPD: got 658th query wrong
Lol it's funny to see submissions of H. A lot of newbies got the logic.
For c problem if anyone needs help in c problem u may read this. -- 1)The path we should follow must be a straight line otherwise the chance of any circle cutting our path would be more,so this is the most greedy way and even u can do little casework to get some idea. 2)secondly suppose we cross a circle at a point in our path in that case circle will reach before us or with us at the final point ( geometric observation) it will never reach final point after us(as it is expanding radially with 1). 3)so we can calculate the distances of every circle center from final point this will be the time for it to reach the final position of our path and if we reached to final point before the fastest circle (circle taking minimum time to reach there) we can always get the answer as yes as we would not have encountered any circle in that case, otherwise we can't reach and answer is no. Hopefully it helps Sorry for my poor explanation skills
D1 can be solved with divide & conquer ?
Thank you for the contest! The problems are nice.
Actually the problems are cool,
But the order...
As for me E < D1 < F1 < D2, so maybe it would be better if swapping D and E :)
how does this O(n * q) solution pass for D1 275884243. I have calculated every nodes current parent according to the permutation and checked it with its original parent
It isn't $$$O(nq)$$$,it is $$$O(n+q)$$$.Because you just use the dfs function once.And in $$$q$$$ queries,because the given tree is a perfect tree,so each vertex only has 2 sons.It won't be TLE.
at the end of each query I am comparing vectors (tp and p) both are of size n + 1. Comparing then will take O(n) hence it will be O(n * q)
Maybe vector's constant is very small,so it can run fast.
Maybe in most of the cases the vector might differ at some smaller indices
hum, when i solved C it's too late for me to solve D, i waste so much time in problem C
there was obvious cheating in last DIV 1 + 2 , this blog explains it — https://mirror.codeforces.com/blog/entry/132571
It's no useful
Hello sir, I have got an email saying my solution coincides [contest:2002][submission:275819490][user:aditya_kh7503] with someone, although i did the whole problem myself, i have attached the proof of my code on the platform, please don't remove my rating and please remove plag from my solutions.
Your text to link here...
Your link is private, consider including the reason/proof in comment itself
Your submission for D2 as well as D1 is exactly the same (you only changed the names of variables, chatgpted into python, and gave values to random things which had nothing to do with the solution) as this one, which was copy pasted from this video on Youtube which 1000 people saw.
Hello Codeforces,
In the last contest, I was accused of cheating in it, specifically for tasks D1 and D2. In that contest, I solved the first 5 tasks. I saw that I was accused with many other people. I see that the way I solved the task is similar, but my way of typing the code is different. This is my 10th contest and in each one I used full names for the variables because it's easier for me to understand and I also use the same template from the beginning. I have not cheated in any of the previous contests, nor in this one, nor do I intend to. According to my submissions, I practiced the tasks in order to improve myself in coding, I did 2 virtual contests where I solved the entire Div 3 and Pinely Round 4 (Div 1 + Div 2) did 5 tasks. Even my first contest was from Epic Institute of Technology where I solved 4 tasks. I don't know how to prove my innocence. So please MikeMirzayanov look at this.
Thanks in advance!
Your submission for D2 as well as D1 is exactly the same (you only changed the names of variables) as this one, which was copy pasted from this video on Youtube which 1000 people saw.
Of course, the submission for D2 and D1 will be the same when I solved D2 and saw that the solution for D2 can also pass for D1. I didn't change anything because, as I said, I didn't cheat. If you look at my coding style I always use full names for variables because it's easier to understand.
You mean you always cheat? Bro please quit, why tf would you tag Mike, he doesn't deserve that. Literally the same code for a problem 244mhq didn't do, ur only changing the name of the variables, at this point admit it please. U ain't slick my guy
Do not use alt accounts. First i will tag Mike because i did not cheat. Second why do you think that if someone who has at this moment higher rating than you and if he does not solve it that does not mean you can not solve that problem. Third like i said i did not copy the code because i coded it.
I asked ChatGPT to change the code from the leaker, and it produced a version very similar to yours. Please stop clowning, it's obvious that your code is line by line identical with leakers.
I love rounds that don't require any special knowledge on most tasks.
I planned to merge the rating, but eventually turned yellow (when I told the girl, she thought that there were liver problems).
I want to go back to Newbie...
Hey MikeMirzayanov,
My solution[submission:275840267] for Problem 2002D1 was flagged as similar to many others. I believe this happened because the problem had very few possible approaches, and I used an AI tool (LLM) to help write some functions because as far as I know there isn't any restriction on using AI generated code on Codeforces. This might have caused some similarities.
I’ve solved similar problems in other contests too, and I’m confident that my solution is unique. I kindly request that my solution be reviewed again.
This blog also states this : Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1. the code was written and published/distributed before the start of the round, 2. the code is generated using tools that were written and published/distributed before the start of the round.
Rating rollback???