Kuroni's blog

Codeforces Round #558 (Div. 2)
By Kuroni, history, 6 years ago, In English

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

  1. ainta (the only contestant to finish all problems!)

  2. dreamoon_love_AA

  3. hank55663

  4. tfg

  5. pmnox

Div. 2:

  1. xht37

  2. Ekoos

  3. beka_asd

  4. bbao69

  5. OIerDb

The editorial is available here. Thank you for participating!

  • Vote: I like it
  • +309
  • Vote: I do not like it

Comments Comments (131)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +48 Vote: I do not like it

I'm still waiting for an anime themed contest.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to get blue v,:

→ Reply
»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

An unbalanced contest, lagging servers and those re-evaluations are the last thing anyone wants.

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the score distribution?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -48 Vote: I do not like it

Я в это время буду на бессмертном полку.

Ставь класс, если уважаешь ветеранов!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

I should have remembered these guys to pull into the comrade setter team back then :D.
Anyway, expecting Hackforces :>

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

again catforces

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

seems to me,the contest must be quite balanced,as the problemsetters have large rating difference

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

May be, It is first time in Codeforces when specialist is one of the problem setter :)

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

4 problem setters with 4 different colors! :)

→ Reply
»
6 years ago, # |
  Vote: I like it -41 Vote: I do not like it

I want to be red

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

will there be a round?

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

please no more delay I'm already hungry(Ramadan problems)

→ Reply
»
6 years ago, # |
  Vote: I like it +127 Vote: I do not like it

I will call this round

Codeforces Round #502 Bad Gateway

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Now the website is running fine. Hope it stays the same way during the contest.

→ Reply
»
6 years ago, # |
  Vote: I like it -58 Vote: I do not like it

unfortunately, all Egyptians Muslims can't join because of our fasting ends at 16:40 UTC+2, and we should eat at this time :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sad part of life..

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you truly believe in your religion's traditions, do them without complaining.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wanna become blue ...but they throw me out even of green community :'/

→ Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

WTF?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Dude wants to become red in three months and you are wasting his time, wtf cf!!

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

At last, Mike solved the issue..Codeforces up again!!.. Good contest isn't cancelled..!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Alive!

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Too strong pretests......

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How the hell did you solve B2?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its the contest, when you solve only 1st problem, you get +rate anyway. Thx

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

So, How to solve D?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 10   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

is C impossible to solve with floats? i kept getting WA 10

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used double instead of float and passed pretests

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah I think so. I think my solution will fail the real tests.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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.

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea about the 15th test for C1 or the 14th test for C2

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 39   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

couldn't submit in last 10 seconds because server wouldn't load :(

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I wanted to submit in the last minute but the submission page didn't load, :(

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone find a clever way at C to not use float or double?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should try GCD.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        try set of pair at every array index for the line aX + bY + c = 0.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't solved C2, but you can store the slope as a pair (numerator,denominator) of an irreducible fraction

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reduce the slopes and intercept to simple fraction, i.e, 10/2 -> 5/1, 5/-1 -> -5/1

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh, I get it. And you were doing calculations with the fractions as pairs of numerator and denominator, right? Thanks for the answer!

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it possible for c to overflow long long?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Not at all. The coordinates were at most $$$10^4$$$ by absolute value, so at worst cases $$$c$$$ couldn't even exceed $$$10^9$$$.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I usually define structure Fraction in this king of problems,

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    To avoid precision errors, I multiplied my doubles by $$$10^9$$$ and cast them to long longs.

    → Reply
»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -49 Vote: I do not like it

This contest should be unrated ! codeforces was unable to respond in the last minute

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So,,, Was F solved with some Edge Replacement Paths algorithm? Is there any algorithm which is easy to CP community? Thanks

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the first time, the harder edition of any problem has less point than the easier edition of it! Good job!

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

b and c didnt have a cool idea but they were really hard code :/

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why do the harder versions have lesser points than the easier versions?

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't solve problem F, any ideas?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Seems that it is well-known "Replacement paths": https://www.researchgate.net/publication/228060271_The_Online_Replacement_Path_Problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I'll read it tonight xD

      → Reply
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

D is quite standard, but E is very beautiful. Kudo to problem E's setter.

→ Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

RESOLVED

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP value can be -1. So you need to use another vis array to check if this state was visited before.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ooh, you are right.

      Thank you for pointing!

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope for blue

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve b??

→ Reply
»
6 years ago, # |
  Vote: I like it +46 Vote: I do not like it

When you get +7 rating

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

come on, test！

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Mike, please remove enough cheaters that I get to CM :pray:

→ Reply
»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

I was warned because my friends and I used kuangbin's materials.https://blog.csdn.net/dllpXFire/article/details/81235703

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this TLE's ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'm not entirely sure but you possible need to override the hash function in your Pair class.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Maybe u've got division by zero or other RTE which is interpreted as TLE here. But i'm not sure.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What is the other alternative to this ? I mean how to store the key value pairs for the straight lines ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it -7 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why some submissions have "invisible" tests? Please make tests for all submissions visible?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why long double fails for C whereas double passes ?

→ Reply
»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I found the constraints a little funny in problem A: n >= 2, but the problem statement says "The three friends"

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply