Hi Codeforces!
I'm glad to introduce you to Codeforces Round 558 (Div. 2), which will take place on 09.05.2019 18:05 (Московское время).
You will have 6 problems and 2 hours to solve them. Two problems will have subtasks. Round will be rated for everyone with rating below 2100. Participants from the first division can also participate out of competition as usual.
The problems were prepared by me, ArguteOnAir, Shirone, and GreymaneSilverfang. I would like to thank cdkrot for his immense help during the round preparation, 300iq, mohammedehab2002, and Um_nik for testing them, and of course MikeMirzayanov for the Codeforces and Polygon platforms.
In the contest, you will meet Kuro, Shiro, Katie, and Selena, the four naughty but smart cats who love playing and asking questions. I hope you will find our problems interesting.
I will be in the community Discord server after the contest to discuss the problems with you. You can find the server here!
Good luck!
UPD1: Problem B and C will have 2 subtasks. The scoring distribution will be 500 — (750 + 500) — (1000 + 750) — 2250 — 2750 — 3250.
UPD2: The contest will be delayed by 15 minutes due to technical reasons. Sorry for the inconvenience :(
UPD3: Final standings!
Div. 1:
ainta (the only contestant to finish all problems!)
Div. 2:
The editorial is available here. Thank you for participating!
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
Идут как-то специалист, эксперт, кандидат и мастер по лесу, видят машина, сели в нее и составили контест
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
I'm still waiting for an anime themed contest.
I'm still waiting for a hentai themed contest.
Basically the same thing /s
There is such. You can upsolve any GreenGrape contest
You wanted hentai contest? Here you are ...
I have fulfilled your wish Sir. Codeforces Round 616 (Div. 1)
I'm still waiting for a balanced contest
I am still waitnig when the tourist not be a number one)
I hope to get blue v,:
same thing bro :/
congrat
orz
An unbalanced contest, lagging servers and those re-evaluations are the last thing anyone wants.
What is the score distribution?
Я в это время буду на бессмертном полку.
Ставь класс, если уважаешь ветеранов!
I should have remembered these guys to pull into the comrade setter team back then :D.
Anyway, expecting Hackforces :>
It will be the first round in Ramadan ,I hope to be a special one
again catforcesseems to me,the contest must be quite balanced,as the problemsetters have large rating difference
May be, It is first time in Codeforces when specialist is one of the problem setter :)
Not quite.
4 problem setters with 4 different colors! :)
I want to be red
Red doesn't want you .
will there be a round?
I hope
I think its better to reschedule it to tomorrow rather than holding it now and making it unrated later
please no more delay I'm already hungry(Ramadan problems)
Please be patient, Mike's worked hard to make the server under control.
Nobody cares
I'm not serious about it lol just joking
religion its your personal problem
Religion is not a problem :thinking:
as for me its a problem
I won't take words from a newbie.
feels racist
*ratist
I will call this round
Codeforces Round #502 Bad Gateway
Now the website is running fine. Hope it stays the same way during the contest.
unfortunately, all Egyptians Muslims can't join because of our fasting ends at 16:40 UTC+2, and we should eat at this time :(
sad part of life..
If you truly believe in your religion's traditions, do them without complaining.
wanna become blue ...but they throw me out even of green community :'/
Good luck bro!
thanks...same to u as well
WTF?
Dude wants to become red in three months and you are wasting his time, wtf cf!!
i believe codeforces platform is all about the top smart guys in the world. So can these smart guys figure out how to provide a stable access and give us a better experience ?
You can formally lay out your complaints to the platform using this link.
At last, Mike solved the issue..Codeforces up again!!.. Good contest isn't cancelled..!
Alive!
Too strong pretests......
How the hell did you solve B2?
using std::set
Its the contest, when you solve only 1st problem, you get +rate anyway. Thx
So, How to solve D?
Fill the dp with 3 dimensions.
dp[i][j][k] = the answer of the problem for C[0..i], such that prefixes of s, t of lengths respectively j, k are suffixes of C[0..i].
i,j are maximum, but i can't be equal to s.length(), similarly j is not t.length()
Count the dynamics by BFS starting from state (0,0,0)
Handle the transition by looking at possible values for letter C[i].
Nice contest, strong pretest (at least for B+, I suppose). However, I felt like B and C was a little bit hard-implementing, and D was quite standard in terms of idea.
Anyway, kudos for the attempt. ;)
is C impossible to solve with floats? i kept getting WA 10
I used double instead of float and passed pretests
I was using doubles as well but I fail pretest on c2, I think the right answer is to use gcd paired slopes or something
Yeah I think so. I think my solution will fail the real tests.
I just found out I failed because I used
intinstead oflong longfor the final answer. Looks like I'll never be good.........I made the same mistake. To make an integer overflow error after having made it a dozen times before... takes a lot of skill, I'd say.
Any idea about the 15th test for C1 or the 14th test for C2
I got WA from 15th test. But after I changed long double to double, I got pretest passed. I don't know why it passed too. High chance to fail system test.
couldn't submit in last 10 seconds because server wouldn't load :(
I wanted to submit in the last minute but the submission page didn't load, :(
Did anyone find a clever way at C to not use float or double?
You should try GCD.
I thought about that but you can only do it for the slope. I needed the whole line equation in my solution. Maybe my solution is wrong.
try set of pair at every array index for the line aX + bY + c = 0.
I didn't solved C2, but you can store the slope as a pair (numerator,denominator) of an irreducible fraction
Reduce the slopes and intercept to simple fraction, i.e, 10/2 -> 5/1, 5/-1 -> -5/1
You can store the line as triplets $$$(a, b, c)$$$ denoting the linear equation $$$ax + by + c = 0$$$, where the parameters could be obtained by calculating difference vector and minimize it by dividing the vector coordinates with its gcd (and also standardize it, by denoting a rule of which parameter should always be non-negative).
Oh, I get it. And you were doing calculations with the fractions as pairs of numerator and denominator, right? Thanks for the answer!
Isn't it possible for c to overflow long long?
Not at all. The coordinates were at most $$$10^4$$$ by absolute value, so at worst cases $$$c$$$ couldn't even exceed $$$10^9$$$.
I usually define structure Fraction in this king of problems,
To avoid precision errors, I multiplied my doubles by $$$10^9$$$ and cast them to long longs.
this is not fair
i knew what is my problem in last 60 second
and i just need to give the code but codeforces is so bad because its Breakdown a lot of time
This contest should be unrated ! codeforces was unable to respond in the last minute
So,,, Was F solved with some Edge Replacement Paths algorithm? Is there any algorithm which is easy to CP community? Thanks
For the first time, the harder edition of any problem has less point than the easier edition of it! Good job!
b and c didnt have a cool idea but they were really hard code :/
Why do the harder versions have lesser points than the easier versions?
I didn't solve problem F, any ideas?
Build 2 min path trees from running dijktra starting from 1 and N (and use the same path from 1 to N in the trees). Let's break the queries into 2 types:
The edge isn't in the min path. This is easy, it's just min(minpath, path using this edge)
The edge is in the min path. The answer is either the path using this edge or some path not using this edge (so it won't get the original min path). The path will look something like (path in the min path tree from 1 not using the queried edge, path in the min path tree from 2 not using the queried edge). For every edge not in the min path, we'll analyse at which "height" (read as height of LCA of the vertex from the edge and the target vertex) of the vertices from the edge at both trees to know where it "touches" the path in the trees. This will turn into a [l, r) range of the indices of edges in the min path that you can overwrite (if the queries edge is before l, it means that the path crosses the edge in the tree from 1 and if it's after r, it crosses the edge in the tree from N). This turns into range updates of minimum and the answer is min(path using the edge, value of this position in the path after min updates).
Not sure about this but it looks correct after glancing at the editorial.
Thanks, I understand it now.
Seems that it is well-known "Replacement paths": https://www.researchgate.net/publication/228060271_The_Online_Replacement_Path_Problem.
Thanks, I'll read it tonight xD
D is quite standard, but E is very beautiful. Kudo to problem E's setter.
how to solve E?
I tried to submit my solution 2 minutes before the end, and couldn't do it because Codeforces servers just stopped working, unable again to survive a few thousands participants. And I just was waiting before the time flew away. It's really frustrating, because I was hoping the developers could get rid of these events since the last time I got such experience (some years ago).
RESOLVED
DP value can be -1. So you need to use another vis array to check if this state was visited before.
Ooh, you are right.
Thank you for pointing!
hope for blue
Nobody cares
Sad Life
If not for the sample test it would be very hard for me to get B Accepted in first attempt.
how to solve b??
When you get +7 rating
My B1 failed on test 55 but B2 passed sys tests. Submitted code is identical. Logically B2 also should fail. So are test cases all different?
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
come on, test！
Mike, please remove enough cheaters that I get to CM :pray:
this but with M
I was warned because my friends and I used kuangbin's materials.https://blog.csdn.net/dllpXFire/article/details/81235703
awsl
awsl
It is easy to see that the codes share not only geometry routine but also the main code which does not included in the published library code.
Ok, thanks. It's too embarrassing
https://mirror.codeforces.com/blog/entry/66921?#comment-510469
почему так? +тесты до сих пор не доступны
Why does this TLE's ?
I'm not entirely sure but you possible need to override the hash function in your Pair class.
Maybe u've got division by zero or other RTE which is interpreted as TLE here. But i'm not sure.
No I can't get RTE as I have considered lines parallel to x and y axis differently .
And this was really awkward "Maybe u've got division by zero or other RTE which is interpreted as TLE here".
In the worst case you will have $$$5 \cdot 10^5$$$ elements in hset and $$$5 \cdot 10^5$$$ elements in tmap. Once I used a TreeSet of Integers of $$$2 \cdot 10^5$$$ elements and it worked in $$$1590$$$ ms. So I do not think that TreeSet of Pairs of $$$5 \cdot 10^5$$$ elements and TreeMap with Double as key fit into $$$3000$$$ ms.
I also do not recommend to use HashSet or HashMap of $$$5 \cdot 10^5$$$ elements. It's easy to hack.
What is the other alternative to this ? I mean how to store the key value pairs for the straight lines ?
Switch to C++. TreeSet/TreeMap are probably some of the slowest data structures known to man. Many problems are impossible to solve without C++. It happened to me before, so I finally switched to C++, and it was definitely worth it.
For reference on slowness: one problem I passed in Java with TreeSet took 950 to 1000ms, while the same C++ implementation with set took 60 ms at the most! And on one particular problem I was trying to solve — nobody had ever written a solution that passed with Java because it required TreeMap. I cranked 20+ hours on that problem and couldn't get it within 4 seconds TL. Finally I switched to C++ and it passed in 1200ms on the first try.
The solutions of other people will answer this question better.
You can try to minimize the number of requests and updates to sets and maps. Then the number of elements will play a less significant role (see 53931811, 53958974 or 53921091).
You may notice that it is not necessary to use a set or map. You can simply sort all $$$5 \cdot 10^5$$$ lines, remove duplicates and count the answer. And it will work much faster than solutions with a set and/or map, although the asymptotics of the solutions are the same (see 53931478, 53938870 or 53951435).
P.S. And yes, there are some problems that cannot be solved using Java. But such problems are rare.
Its too bad when this results in loss of rating because of this : "there are some problems that cannot be solved using Java". Last day I started with C2 in order to gain some extra points but this just ruined the contest for me. Lastly I saw B was way much easier to code.
Why some submissions have "invisible" tests? Please make tests for all submissions visible?
Started contest with E and was solving it for 1:45. Then upsolved other problems and submitted them arter contest
Cudos authors for contest, it was really interesting!
Why long double fails for C whereas double passes ?
I found the constraints a little funny in problem A: n >= 2, but the problem statement says "The three friends"
"Ваше решение 53921651 по задаче 1163B2 значительным образом совпадает с решениями других участников и находится в группе одинаковых решений GolD_Batyr/53921651, dinesh_gvp/53921769. " Мой ответ: Сравните шапку(шаблон) кода 53921651 и {53789827, 53916369, 53788308}, они идентичны. А теперь посмотрите шаблон решения {53761427, 53758013}, которые были написаны dinesh_gvp. И я никогда не использую "return 0" в конце кода, чего не скажешь о решениях dinesh_gvp({53627491, 53912625, 53754680}). Думаю, этого всего достаточно, чтобы убедиться в том, что код был написан именно мной. Что же касается того, как у меня скопировали код, то я использовал ideone.com и совершенно не знал о том, что можно красть чужие решения, и впредь буду знать.
btw, ronaldo > messi
Why some participants passed B2(hard version)? But their code couldn't passed B1(easy version). Are the test cases in B2 weak?