Hi Codeforces!

I'm glad to introduce you to Codeforces Round #558 (Div. 2), which will take place on May/09/2019 18:05 (Moscow time).

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, _iloveNQ_, _Shirone_, and LunarStellarshot. I would like to thank _kun_ 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'm still waiting for a balanced contest

I am still waitnig when the tourist not be a number one)

I M STILL WAITING FOR A UBISOFT CONTEST

I hope to get blue v,:

same thing bro :/

good luck :D

orz

Cookie

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 :>

As above description of the contest, we can consider problems as Tom and contestants as Jerry :D I wish there could be a ludicrous fight in this contest :P

Pussy i.e Cats are always naughty. ( ͡°❥ ͡°)

It will be the first round in Ramadan ,I hope to be a special one

~~again catforces~~seems 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

lol you're a blue newbie

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..

you are right

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

food is ready but you have to wait ha ha ha ha.......

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

can you explain your approach please ?

I solved cookie (0) problems this round

Why no one upvoting me?

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 ofs, tof lengths respectivelyj, kare suffixes of C[0..i].i,j are maximum, but

ican't be equal tos.length(), similarlyjis nott.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

`int`

instead of`long long`

for 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

juststopped 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).RESOLVEDDP 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

Before: Yeah, I will get a high rating! After: QAQ

What is this. Who am I. What am I doing.

If not for the sample test it would be very hard for me to get B Accepted in first attempt.

nvm, it was reverse, sol is wrong

What's Test Case 42 in problem A, Lot of solutions failed at it :|

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://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".

Maybe u're right I just remembered that one on the contest. I've got TLE when work with ordinary array in c++ and trying to read out of bounds. It wasn't std::vector which throws std::out_of_range and I've got UB. So I was writing thinking about that case. Actually I also understand that in Java you can't have similar problem but still I had some doubts about testing system. I also think he is right.

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?

https://codeforces.com/blog/entry/66921?#comment-510469

mb thats why

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"

Why some participants passed B2(hard version)? But their code couldn't passed B1(easy version). Are the test cases in B2 weak?

because they ate their cookies

How to solve B2? I don't understand the editorial.