Hello codeforces!
I'm glad to announce that codeforces round #478 for the second division will take place on Tuesday, May 1st 17:05 MSK. First division participants can also take part out of competition.
Great thanks to Nikolay Kalinin (KAN) and Fudail Hasan (fudail225) for helping me prepare the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform, Many thanks for Amr Mahmoud (RetiredAmrMahmoud ) Tameem Zabalawi (timo14z), AmirReza PoorAkhavan (Arpa), Alexey Ilyukhov (Livace), Hag Ahmad (Reckt), Nikita Bosov (FalseMirror) and Andrew Rayskiy (GreenGrape) for testing the round.
You will be given five problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!
I hope you'll enjoy my round. I wish everyone good luck and high rating!
UPD1: problem scores: 500 — 1000 — 1500 — 2000 — 2500
UPD2:
Congratulations to the winners
1- kmjp
2- TangentDay
3- Llamap.
4- E869120
5- kevinsogo
Div.2 winners:
1- Llamap.
2- amarDhcuMoS
3- phongthan
4- Nirma_Sucks
5- MagolorSoul
UPD3 : Tutorial is out!.
Yeah! 3 contests in 3 days!
[Can I go back to Purple again?]
Yea Already you have backed your purple color. :D :D :D
is it round #473 ? thanks :D..updated :)
I smell math problems :\
Good news for EleCursity :D
Great news for EleCursity, NourAlhadi and SubSpring.
Acceptophobia 8 Solved Problems Mo Salah 6 Solved Problems Dude you really need an efficient cheating algorithm :D :D
Every round is a good round for a cheater...
repeating math is your game (odd*odd = even)#3tees
The new Math_Master
[user:DT_Kang]he can solve all math problems
why? Because Rollo?
I told you :)
I love math, but is it rated?
Hmm, I think it is rated
Otherwise, he would have written that it was unrated.
Yes, It is.
.
A Syrian contest :D
It's a good gift in my birthday "Codeforces Round".
Codeforces is just a gift that keeps on giving :)
I wish everyone high luck and good rating!
It is not possible for everyone with high luck and good rating.
Bcs someone will be a bad rating, for this reason, someone will be good rating :D :D :D
So your statement will be definitely false.
When does the system test begin? :)
UPD: It is system testing now!
Maybe it will be like Round #464？
After the round, the following sequence of events will happen: system testing of Round #464, system testing of Educational Round #38, rating updates for the Educational Round, rating updates for Round #464, in that order. Ratings for Round #464 will be updated for participants who were in div. 2 prior to the Educational Round.But I hope the system test of Edu Round will come before the Round.
I think they decrease open hacking phase time just in order to begin system test before Round 478 :)
( Sorry for my poor English.
KAN no math test please, this isn't high school
good contest = IMO contestants = math = math = math ...
There is a little mistake. In second sentence you wrote «round #473»
Upd: fixed
Come on, he pointed out a valid mistake in the announcement. Stop downvoting him.
The scoring distribution will be published soon = u will know when the contest will start prove me wrong..
3*
Today i will get atleast(-100) in my rating.
Ratings are not everything. We should give our best in every contest and keep learning :D
May god save me in my exam tomorrow.
When will the rate changes appear?? Im dieing over herew
with the system testing of educational round, i am back to purple. now if i attend this round whether my rating for this round will be discarded or this round rating will be updated first and then the educational round rating will be applied compared to this rating.
This has happened before and the rating changes of both contests were based on the rating before edu round.
You can actually hit orange if your rating is ~1900 and you are top 10 in both div 2 contests.
Edit: Looks like they fixed it this time.
So much Love xD :D
No more dynamics in Competitive Programming please :(
this is shit
what a bullshit geometry contest :/
This is pure shit :)
If you mix some shit, geometry, physic and implementation it will be great contest, isn't it?
The comment is hidden because of too negative feedback, click here to view it
Why don't you prepare a round then instead of bitching?
From my point of view (tester’s, not author’s) this contest is well designed and properly balanced. Yeah, I personally hate hard geometry (but there’s only one such problem here and it is E, so it isn’t supposed to be solved by many, what’s wrong then?), but I can assure you that there are things I loathe much more — haters, for example. Most of you haven’t even committed anything to codeforces — how dare you speak this way?
People's lives should not be a part of a joke!!
Keep your comments out of CF
Honestly the last two problems are really great, but its not good to see them in the same round, i just withdrawed the round when i saw the shapes...
I did nothing for 3/4 of the contest because of the geometry. I think 1 problem of geometry is fine if there are other problems of which to think about.
You can't just quit a problem because it has X Y input or happening in plane and say its geometry About 350 people solved it And its just some pen/paper linear equations
You are right. My mistake.
What a Round of codeforces. UPD: This Round Has very less amount of hacks :D :D :D
Some people managed to get successful hack. Example: ZeroTwo
Yea. But Why Hacks list is null?
There have been 9 hacks in this round. Go here and select Any Problem -> Hacked on the right side and hit apply button
In the hack list, you can see just your hacks. It is not like educational rounds.
But you can do like latvian said.
Oops! I am really don't know this.
Thanks for your information.
Can anyone give me a hint with D? :)
I guess it's hashing
Can you clarify your point?
Well, two points collide if (Vy2-Vy1)/(Vx2-Vx1) = a, so we need to calculate how many of points satisfy this, but there is also case when Vx2=Vx1. I am missing something probably, but idk what
After that you can map every point with a*Vx-Vy and do something, but there are some collisions i guess...
Nvm there is correct solution below this
Btw what is Test 8
I got WA on test 4 actually :D
For collision for two ghosts (let their indexes be i and j), we should have xi + t * VXi = xj + t * VXj and
a * xi + b + t * VYi = a * xj + b + t * VYj
After simplying we get
xi - xj = t * (VXj - VXi)
a * (xi - xj) = t * (VYj - VYi)
and dividing second to first
a = (VYj - VYi) / (VXj - VXi)
So, we need to find count of indexes i and j such that slope of them equals to a. It can easily done by compression and something like two pointers or BIT.
We can use only maps =) here
Of course, but my teacher MR. MSHus (a.k.a. computerbox) taught me to overkill everything. He's the best teacher in the world so my account is named for the honor of him. WORLD NEEDS TEACHERS LIKE MSHus (a.k.a. computerbox).
How i can be your teacher my friend ? :) Maybe are you my fan number one ?
MR. HACIYEV is so shy and modest man so he considers all of his students a friend. MAKE WORLD GREAT AGAIN WITH TEACHERS LIKE MSHus (a.k.a. computerbox)!!
Another condition is that VXi ≠ VXj.
Also,
. So C++ map and inclusion-exclusion is enough.
I did that and got WA8
You can see my implementation here
Dude, when I see this and my implementation...
Problem can be simplified by mapping the line y = ax + b to the X-axis using a shear. Now all ghosts are on the X-axis. Two ghosts can collide only if they have same Vy, so group them by Vy. If two ghosts have same Vy the problem reduces to 1-dimensional case where two ghosts always collide except if they have same Vx. And that's it.
I was thinking about rotating the line to X-axis, but I didn't know enough geometry and had to go for dinner :P SAD!
Using a rotation instead of a shear should also work theoretically but the floating-point error devil would probably not let you slip by :P
Finally understanding the solution. Wonder why I spent my time thinking of some complex geometric scenarios.
Thanks all of you! :D CopeCope, BFF, mochii, xuanquang1999, meooow.
(Sorry for the late reply, I was forced to sleep like, immediately after the contest ended :-P )
What is the 4th test in E?
test 4 in D?
What is the idea behind D ???
http://codeforces.com/blog/entry/59186?#comment-427772
what is pretest 3 in B
never mind...got it :(
I think that it is something like:
2 2 0 0 0 0 0 0 0 0 0 0 0 0
and you don't clear one of the "2" elements before you distribute its value, or you consider the "0" elements (whereas you shouldn't consider them).
That's not a valid test case. From statement: "is either zero or odd"
Oh sorry, you are right.
I'll edit my comment.
Thanks :)
Something like 49 0 0 0 0 0 0 0 0 0 0 0 0 0.
My mistake was to forget about setting to 0 the cell which is used for getting stones.
Есть какие-нибудь догадки на счёт 4 теста в C?
думаю, примерно такой тест:
ответ:
I, for one, thought this was a pretty cool contest and am happy to see someone writing geometry problems. Personally, I think that CF has the best platform of all the competitive coding sites. The main problem I have with CF, though, is that the problems tend to be very narrow in scope (segment tree, basic number theory, dp and graph problems cover like 90% of the div 2 tasks that along with the "non-algorithmic" implementation/greedy/simulation). Geometry is such a rich area of algorithms and there are so many cool algorithms that you can build problems around that I feel like we often miss out on a lot of cool problems by almost never having geometry questions. So thank you, Odin-, for writing a contest with some cool geometry problems, because, in my opinion, CF could benefit from having more of those.
Problem C , WA test 8
http://codeforces.com/contest/975/submission/37819859
why!! :(
k should be long long
Should all participants in competitive programming know about torque/equilibrium formula or have a bad time to figure out what happens when "one point is fixed... blahblah?"
I really want to see problems only using computer science/engineering knowledges. What's the point of giving the problem with 90% physics + 10% implementation?
I agree with this. There should be a more specific description about when the object is considered 'balanced under gravity'.
Otherwise, saying that the contest is geometry bullsh*t because of not realizing that D doesn't require geometry knowledge is just nonsense (I'm not targeting you).
There are no hard physic formulas at all. All you need to solve the problem: 1. When "one point is fixed... blahblah?" center of mass moves to point directly below the fixed point. 2. The center of mass of rectangle = weighted mean of the centers of mass of triangles (0, i, i+1)
For you, it may be easy physics. For me(and maybe some other contestants), it's not. In Korea, there's no class about torque in mandatory school class. Is it about computer science? No.
That's why this problem is nonsense.
How about chemistry? biology? "Print the year when World War II occured."? I believe this problem is same with those cases.
In the solution there is no use for torque, angular velocity, Friction force ... etc because those are advanced physics topics. from the sample tests you can develop an idea how things work. I mean it is very obvious from the first sample that the polygon rotates around (2,0) and its center of mass will be right under the pivot (2,0).
Maybe you are not familiar with center of mass of a geometrical shape. I think you just have to read about it. Its very useful and easy. Center of Mass
I hope that now you know about these stuff and maybe in ICPC you can solve some problem that use the same physical principals.
err, that's exactly the problem. People need to know about the center of mass to solve the problem. This will give an unfair advantage to people who are well verse in physics compare to those that are not. Also, people who are familiar with physic may also know shortcut to the solution(maybe using torque or something). I think the argument here is that a CP contest should not involve any physics at all.
Actually you can figure it out from observing how the polygon in the sample rotate.
Anyway, Now you know.
I know it in the first place, this is about people here who are not well verse in physics.
So you are telling me I can discover what a center of mass is just by an example? How do I know if it's a coincidence of something?
I think you are ok with this because to you it is common knowledge. But the problem is common knowledge across the world is different. Suppose now I change the question to I have X and Y chemical, which form Z chemical(basically some chemistry stuff), and I give you their mass and equilibrium constant, and ask for their final mass(I might be wrong, I forgot my chemistry). This may be a common knowledge to me, but it might not be the case to others. And the key point of solving such problem is on the chemistry, and not idea.
I think the least you can do is to put such information in the problem. I have nothing against it as I barely do contest anyway, just trying to express what I see people are feeling.
Hmm, It is math! incenter of a triangle is well known in math. you can use it to find the centroid of a polygon.
Actually it's not about torques, it's about fact that equilibrium point is the one in which potential energy is minimized and that we can use only center of masses to calculate system's potential energy. That would be enough to solve the problem and I consider it as common knowledge.
The most hard thing is probably determining center of masses for solid body... But, at least in Russia, it is covered in many algorithm resources, like famous e-maxx.ru.
I'm not sure that all participants should know it, but I think that problem is totally fine. As well as problems in which you have to deal with discrete analysis, number theory, general algebra, linear algebra, mathematical optimization and numerical analysis.
If we extend your point of view, we can say that problems which need 90% combinatorics and probability theory + 10% implementation are bad. Is it so? I doubt that. So why would it be ok to make a problem based mostly on advanced maths but to make a problem based on basic physics is bad?
P.S. If we go further, this question seems to correlate with what is participant's aim in competitive programming. If you're here just to compete and earn high results, then yeah, it would be better for you if contests had strict syllabus restrained to mostly theoretical computer science and some basic maths. But my main purpose is to study new designs, so I highly appreciate problems that involve some new and unusual ideas and concepts.
So... To consider if some problem is ok for contest or not, we should start with defining the purpose of contest itself. For div. 2 contests I believe educational part is more important than competitive, so in this particular case it's just perfectly ok.
it's about fact that equilibrium point is the one in which potential energy is minimized and that we can use only center of masses to calculate system's potential energy. That would be enough to solve the problem and I consider it as common knowledge.
common knowledge? I guess common knowledge in different region is quite different, this is really the first time I heard of this, and I did physic until Pre-University(A-level)
It's the same as "1. When "one point is fixed... blahblah?" center of mass moves to point directly below the fixed point."
And yes, I hope It's common knowledge.
Can you provide definition of "computer science/engineering knowledge"? Are math-heavy problems fine in such case? To avoid writing long comment here, I'd just say that I pretty much agree with adamant.
On a side note, I also find both D and E being ugly. But that's a matter of taste.
Wow look at this solution someone wrote a case hackme for n=696
http://codeforces.com/contest/975/submission/37804303
HAHAHAHAHAHAHAHAHA
It seems that someone is attempting to bring dishonor to my name...
Great contest, loved it. Really short solutions, I've got 60 lines in total for A-D and only 100 in E.
Problem B, Test case 10... It took half hour for me to pass that test. Probably it requires using long, not integer. Since a possible sum of stones like 13*10^9 can not be stored in int. Sad contest for me :(
In problem E, what if we have 3 points: (0, 0), (1, 1), ( - 1, 1) and fixed point is (0, 0)?
this equilibrium is not stable so it should rotate.
I would like to report BorisYeltsin and vammadur for using unfair means. He hacked vammadur whose code was clearly written to be hacked. I am not sure if it is the same person but it seems very fishy. Have a look at his submission 37804303
Seems they are not the same person, vammadur just solved A to get minus hacks, and also wrote this case to get hacked to lose more points. Congrats, BorisYeltsin, for using this opportunity :P
If it is the same person, I wonder how he could arrange both his accounts to be in the same room.
you just need enough accounts and enough tries.
But for this case it's not, he seems to be doing this a few contests ago.
Can anyone help with me C?
Your code is brute force... Please use binary search to get index till which person is killed. For c++ you can use lower_bound() as well as upper_bound() for inbuilt binary search.!
Cheers
Problem C can solve with binary-search as follows:
Here is my code: Code
I did my binary search but still got TLE. Anyone else uses python for C? I assume python is too slow for this?
37819860
It is very likely because of the high amount of I/O in the problem. You can try to find some optimised IO implementation somewhere like there are for Java.
Also, Python has inbuilt binary search (
bisectmodule). Maybe it will offer better performance than your implementation.lastly, you can choose PyPy as your language — it is compatible with Python2. PyPy is compiled down to native code and is hence faster.
I tried the bisect module, it indeed runs faster and my code got accepted. Haven't really explored some other IO options, will check them later I guess. PyPy runs slower for some reason, I have no idea.
Anyway good to know, thanks!
Same problems, same submission times, but not the same ranking, unfortunately. :(
Wow ! Quick sys test (Y)
Hi, I got pretest 8 passed for problem C and my code number is 37815677. But I got a TLE on test 8 while system checking. I submitted the same code again (37820871) and its showing AC for the same code. Can someone please provide me a satisfactory response for the same.
I even compared the two codes on codeforces in the compare section and they were termed as identical. If it was some system bug, my code should be re-evaluated and given an AC.
Hey, guys. Can anyone tell what is wrong with my C solution? I decided with the help of the dynamics is preserved how much damage to kill of the i-th warrior and how much total damage of the arrows, until they kill everyone.
Solution: 37817808
Next test give you a wrong answer: Input: 5 6 3 4 5 6 7 1 1 1 1 1 Your Answer: 5 5 4 4 4
I'm not sure if the rating changes is not correct.
But I'm just asking you, please, to ensure from it.
Within the contest, when my rank was a little more than 700, the "Rating Changes Predictor" told me that my rating will change by +30, and now after the end of the whole system test my rank is 609, but my rating changed by +29!
I solve 3 tasks and my rating was decreased.
To be honest, as I know, the change of someone's rating depend on his/her rank, not just on the number of the solved problems.
And the rank depends on the score, which depends on the solved problems, the time he/she sends the last correct submission for a problem and the number of distinct failed submission (except the failed submissions on the first test).
MikeMirzayanov, хочу обратить ваше внимания на возможное читерство со стороны chdn . Его тиммейт AndrewB330 по множественным олимпиадам, в том числе и командное участия на Vk Cup. Второй участник сдал задачу Д на 1:01, а chdn сдает эту же задачу на 1:04. Кода не совпадают, но есть вероятность обмена идей и решений.
а еще у них разница между сдачами задачи B десять минут! это просто наглость какая-то — двум тиммейтам решать одну и ту же задачу! я требую лайфтайм бана для них
Уговорил, я таки решил глянуть что не так с моим кодом. Так вот. Что самое смешное? Он неверный)
На этот тест он выдает 0. Это кстати еще один вопрос к силе тестов.
Can someone please tell me why my solution of C gets TLE? I am doing binary search on the prefix sums.37821182
I think your Binary Search function is causing this TLE, because of infinite loop in certain test cases.
thank you!
is it legit that 80% of div2 winners created their accounts 1-2 days ago? The last guy looks suspicious tho
It seems that the contests will not be too frequent then. :D
Maaaaaaaaaan, I am falcon now. Thank yall codeforces.