Привет, Codeforces!
Мы рады пригласить вас на Codeforces Round #572, который состоится в пятницу, 5 июля в 18:05. Раунд будет рейтинговым для обоих дивизионов (так как MikeMirzayanov спасибо в этот раз мы сказали).
Раунд готовили мы, antontrygubO_o и 244mhq. Это наш первый контест, и, надеемся, не последний!
Спасибо arsijo за отличное координирование раунда, gepardo, Mediocrity, kefaa, zoomswk, ecnerwala, AllCatsAreBeautiful, gop2024, Markellonchik, dasfex, taran_1407, ankeet, DenisPushkin, austrian_artist, mmello, sas4eka за тестирование и ценные замечания, а также Михаилу MikeMirzayanov Мирзаянову за отличные платформы Codeforces и Polygon. (please rated)
В каждом дивизионе будет предложено 6 задач и 2 часа на их решение. Настоятельно рекомендуем прочитать условия всех задач! Мы верим, что разбалловка раунда будет объявлена до начала раунда.
Всем удачи и высокого рейтинга!
UPD1: Вскоре после окончания соревнования, мы будем на сервере Discord для обсуждения задач.
UPD2: Небольшие изменения: участникам в Div $$$1$$$ будет предложено $$$5$$$ задач, одна из которых будет иметь $$$2$$$ подзадачи, а участникам в Div $$$2$$$ будет предложено $$$6$$$ задач, одна из которых будет иметь $$$2$$$ подзадачи. Обратите внимание, что в этот раз подзадачи будут необычными, так как будут отличаться не только ограничениями.
UPD3:
Разбалловка Div $$$2$$$ раунда: 500 — 1000 — 1250 — (500 + 1250) — 2250 — 2750
Разбалловка Div $$$1$$$ раунда: (250 + 750) — 1250 — 1750 — 2250 — 2500
UPD4: Разбор
UPD5 Поздравляем победителей!
Div 1:
1. Um_nik
2. ugly2333
3. Radewoosh
4. Marcin_smu
5. Endagorion
Div 2:
1. CSWhisky
2. handsomeIvan
3. philologist
4. teamskiy
5. NeoGul
5 июня?
Early blogs !! best of luck !!!!
deleted
downvote !!! that's my luck .
Savage : (please rated)
The round will be rated for both divisions (as this time we thanked MikeMirzayanov).Everybody takes it seriously now!We strongly recommend reading statements of all problems!Hope that the problems are correctly sorted according to difficulty.
When people downvote for no apparent reason. :(
guys, can you prepare solutions of problems beforehand so we can see solutions immediately after the contest??
But solutions everytime is ready before the contest cause how authors get right answers on tests?
Savage...hahhahah
why I m getting downvotes continously just for saying savage...? Any particular reasons
Why is this downvoted even though it is perfectly fine and resonable question? It makes much more sense for authors to release editorials right after contest, cause after two weeks just a tiny fraction of participants will still be interested in reading them.
Well, editorial is already ready anyways :)
We plan to post it not later than in $$$10$$$ minutes after contest's end
It's cool! But it is not every time that problem setters publish their editorials just after the contests.
I think Codeforces shouldn't accept rounds without editorial been ready, days after the contest most of the time I lose the passion to read the editorial :(
I hope the statement as short as the blog :)
love short statement with no long story else I will submit sample :>
love short statement? how about love story statement
How just about love stories or love letters
how about this problem?
But if you can't solve the problem a good story might cheer you up :)
я уверен что все будет классный
Best of luck for your first contest
The comment is hidden because of too negative feedback, click here to view it.
Nope
then,are u NaCly_Fish?
Someone used this fake username. This is not real NaCly_Fish.
I think you are not real NaCly_Fish...
Will I be able to participate in division 2?? I'm new to codeforces.
Of coures you can.
You can be able to participate in division 2 if your rating is lower than 1900.
tmwilliamlin618 has not participated in the codeforces round yet. So he has no specified rating. (Though that kind of users also belong to Division 2 because in that case the user's rating is considered as 1500.)
I suggest you register another account with a different username and forget about your current account. I learned the hard way that having "tmw" as a prefix and a permutation of "168" as a suffix of your username will give you a significant disadvantage.
Hurry, before it's too late.
Yet you still became IGM and qualified from for the USA IOI team.
All you're doing is proving that you deserve to be LGM, but your username is holding you back.
The significant disadvantage is actually that your rating will be much higher than your skill, not the other way around. People will expect you to do much better than you actually can in non-codeforces contests (like IOI) and you will be given a lot of pressure, especially when you fail to meet their expectations.
Tmw orz
Don't worry we will always love you tmw <3
Поздравляю с первым контестом)) Congratulations on the first contest))
Lets do it!
This is the result of a few refreshments on the page.
I think these differences should be corrected.
this is truly a player who believes in submitting at 1:59:59
You're a witty man. Anyway, I didn't mean to write with such an idea. :)
What about hacking at 1:59:59? ("is it correct?" during 1:50:00 to 1:59:58)
There is a "truly player" who submit at 1:59:59 :)56590817
It's really fun to join a contest after completing my final exam.Good luck for everybody.
once I post the same statement , I got approximately 30-40 downvotes...
deleted
hahah...True
what happend?
Subtasks will be unusual? Oh,that's fun.
Although it's not a good time for Chinese. I still wish everyone have fun and I wish the authors' hard work get success!
when everyone is getting downvotes but u still have 0 contribution
good job, you just joined us.
Seems like some guys are really having fun of downvoting everybody everywhere(
Codeforces: Sponsored by Telegram
As a Chinese,it's hard for me to understand the descriptions in English.
But U can understand it through translators like This and stuff on the Internet. Or U can just work hard on learning English(as a mid-school student in China, I always do this)
UPD3: Contest has been delayed by 10 minutes :)
UPD3: Contest has been delayed by 10 mins :)
are my eyes blind? why it shows
and 49 + 15 = 64?
oh no arsijo again ;/
I just missed this contest, because I stupidly assumed the announced time was on the same timezone as recent contests. Most contests recently have been announced UTC+1 (London time), whereas this one was announced on Moscow time.
Any timezone would do, but it would be good if Codeforces used a consistent timezone for announcing contest start times.
Amazing contest.
Thx for the good contest
contest started in time wow,CF started improving
Nice contest. Thanks :)
Loved watching standings for 2hrs.
Your Solution to Count Pairs is awesome. ;)
I was expecting you would submit it anytime.
I was also watching leader board for almost one hour and then the idea struck me in last 6 mins.
Half of Div1 was judged by a single problem, and even that problem is also a bad problem that relies on one observation.
How to solve Div.2 E?
Hint :$$$(x-y)(x+y)(x^2+y^2)=(x^4-y^4)$$$
Just idea — lated for submit:
Let's iterate over a.
Fix ai. Then you have cube equation aj^3 + Baj^2 + Caj + D ~ 0 (mod p). I assume that at least one root has to be in interval [1..1000] or [p — 1000..p]. Let's say you found that root r. Then you can reduce to square equation. And square equation can be easily solved.
P.S. Sorry for this dumb reply). That was really easier than I assmued
Multiply by (x1-x2). You now have (x1^4 — x2^4) = k(x1 — x2) (mod p) this gives (x1^4 — k(x1)) — (x2^4 — k(x2)) = 0 (mod p)
So you just calculate x1^4 — k(x1) for all indices then just select any two with same values.
Wow, very lame math problem.
Is this idea anywhere remotely close to correct solution for D2 — For any non-leaf and non-root node : Let X be the weight between node and its parent. Then after subtracting some values v_i whose sum is equal to X from edges between node and child, if we can divide them into two parts such that their sum is equal we proceed doing same thing.
I surprised how easy was Div1B and why this low count of people solved it.
The curve isn't very beautiful, but the problems are still really interesting! Thanks for the amazing round!
$$$(a + b)(a^2 + b^2) = \frac{a^4 - b^4}{a - b}$$$
How on earth are we supposed to know this?
This problem is more math than cp.
Look at roots of polynomial :D ($$$a=-b$$$, $$$a=ib$$$, $$$a=-ib$$$) add $$$a=b$$$ for symmetry.
I found it by noticing that
$$$(a + b)(a^{2} + b^{2}) = a^{3} + a^{2}b + ab^{2} + b^{3} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{1 - \frac{b}{a}} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{\frac{a-b}{a}} = a^{3} \frac{a - \frac{b^{4}}{a^{3}}}{\frac{a-b}{a}} = \frac{a^{4} - b^{4}}{a - b}$$$ by the formula for geometric sum.
No, it's not so hard to get the answer. As we all know (a+b)(a-b)=a^2-b^2,so that we can use a^2 and b^2 to replace a and b,so that (a^2+b^2)(a^2-b^2)=a^4-b^4,and a^2-b^2=(a+b)(a-b), so so that (a+b)(a-b)(a^2+b^2)=a^4-b^4, so we can get the answer.
That's just a difference of two squares,but why does it be related to the problem?
Well, I think the formula $$$a^2-b^2 = (a-b)(a+b)$$$ is taught at 6'th grade (at least in Azerbaijan). So, $$$(a+b)(a^2+b^2)=\frac{(a+b)(a-b)(a^2+b^2)}{a-b}=\frac{(a^2-b^2)(a^2+b^2)}{a-b}=\frac{a^4-b^4}{a-b}$$$
Grade school math.
Cant wait for the editorials....can anyone tell about the logic of Array beauty question F in div2?
The main idea is the beauty won't exceed $$$\frac{100000}{k-1}$$$, then you can use $$$\mathcal O(nkbeauty )$$$ dp to solve it.
Fast System Test Start. :)
Editorial is up!
We hope you enjoyed the contest even though differences in difficulties were unexpected (with so many testers lol :D )
I enjoyed staring on the scoreboard.
thanks for the early editorial
Solution for D1: Count the degree of each node and check if there's a node having degree equal to $$$2$$$. If yes, the answer is NO. Else, the answer is YES.
please , explain proof.
Editorial is already out. Please refer to that.
Can problem C is solvable using segment tree ?
you can find the sum using seg tree
why the answer is the (sum of [L,R])/10 ?
check editorial, there is a proof
How can we get this configuration ?
Note that edge between B and F has odd cost, which is prohibited by problem statement.
With integer weights, it's impossible, note that the problem statement specifies that all numbers are even.
With real weights, add for example
Okay. But for DIV2 D1 it says
Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations?That statement doesn't contradict with the example above.
What about it? mango_lassi's answer shows that the answer is YES
In D1 you can use real weights in your operations, while you can't in D2.
Thanks for awesome round!!! Problems are really interesting
So Problem C is solved by one observation that the answer doesn't exceed $$$\frac{100000}{k-1}$$$... I was thinking about how to update the dp in an efficient way throughout the whole contest ... well played.
I came to that almost immidiately and then kept thinking about making an $$$n*maxBeauty$$$ dp $$$k$$$ times or $$$k*maxBeauty$$$ dp $$$n$$$ times until the end of the contest. And then i look at the solution and see "do $$$n*k$$$ dp $$$maxBeauty$$$ times"...
For Div2 B, this program passed system testing but I'm pretty sure it can be hacked with the following testcase:
3 1 2 3
56565011
first 3 is for n ? if your answer is yes so it's of the same type of 3rd sample
Yes the first 3 is for n. I just couldn't figure out how to write a line break there. The program outputs yes but the answer should be no.
this should be enough to output no and this is what i got after trying this test on your code in custom
That if loop doesn't run with my testcase above. Once sorted, arr[] will be equal to {1, 2, 3}, so the if loop would be checking if (1 >= 2 + 3) which is clearly false. The program thus would print out YES which is wrong, as 3 is not strictly less than 1 + 2.
this is what i thought first, but in your template you wrote
oh that's my bad then. That explains why it passed system testing. Thanks for the clarification.
Was locking problem D in div 2 prohibited?
Locking only D1 was prohibited as it was required to solve both problems before hacking
In my opinion, div2 D1 has really weak pre tests. I submitted a solution checking if there was a vertice with degree == 2 as a father of a vertice with degree == 1. And it passed ... luckily I noticed it a 1 minute before de end of the contest, and corrected it ...
I believe you :D
i should read E instead of wasting all my time in D :c
Insanely fast! I'm on vacation in Asia and this contest started past midnight, now I can go to sleep without sweating the whole night about how the systests turn out :)
There is a huge mistake for Div2 D2. If a node has degree 2 and the weights on both sides are equal then it is possible to still construct a tree
Example :
This is a simple tree, we can do the operation
2 3 2and construct the weights of the tree. But I tried this testcase on a number of peoples solution and they printNO.Edge values should be pairwise different.
your input is invalid. weights in all edges must be distinct and even
When this is the only test you fail in A2
Within an hour rating has been updated. Best and fastest checking ever.
Haha, that's because nobody solved anything!
Good problems.
Problem C was interesting. I solved it using segment tree. Saw some others solving it with DP and some with cumulative sum technique .
Cool
добавьте тест для (add test for)D2: 4 1 2 0 1 3 0 1 4 3