_Kuroni_'s blog

By _Kuroni_, history, 5 months 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, _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:

  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

»
5 months 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).

»
5 months 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).

»
5 months ago, # |
  Vote: I like it +48 Vote: I do not like it

I'm still waiting for an anime themed contest.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to get blue v,:

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the score distribution?

»
5 months ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

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

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

»
5 months 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 :>

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

again catforces

»
5 months 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

»
5 months 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 :)

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

4 problem setters with 4 different colors! :)

»
5 months ago, # |
  Vote: I like it -41 Vote: I do not like it

I want to be red

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

will there be a round?

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +127 Vote: I do not like it

I will call this round

Codeforces Round #502 Bad Gateway

»
5 months 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.

»
5 months 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 :(

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

WTF?

  • »
    »
    5 months 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!!

»
5 months 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 ?

»
5 months 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..!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Alive!

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Too strong pretests......

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How the hell did you solve B2?

»
5 months 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

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So, How to solve D?

  • »
    »
    5 months 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].

»
5 months 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. ;)

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used double instead of float and passed pretests

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.........

          • »
            »
            »
            »
            »
            »
            5 months 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.

»
5 months 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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
5 months 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, :(

»
5 months 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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should try GCD.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

  • »
    »
    5 months 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

  • »
    »
    5 months 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

  • »
    »
    5 months 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).

    • »
      »
      »
      5 months 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!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months 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$$$.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I usually define structure Fraction in this king of problems,

  • »
    »
    5 months 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.

»
5 months 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

»
5 months 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

»
5 months 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

»
5 months 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!

»
5 months 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 :/

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't solve problem F, any ideas?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I understand it now.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I'll read it tonight xD

»
5 months 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.

»
5 months 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).

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

RESOLVED

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ooh, you are right.

      Thank you for pointing!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope for blue

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Before: Yeah, I will get a high rating! After: QAQ
What is this. Who am I. What am I doing.

»
5 months 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.

»
5 months ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

nvm, it was reverse, sol is wrong

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve b??

»
5 months ago, # |
  Vote: I like it +46 Vote: I do not like it

When you get +7 rating

»
5 months 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?

»
5 months 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).

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

come on, test!

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this TLE's ?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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".

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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 ?

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.

»
5 months 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?

»
5 months 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!

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why long double fails for C whereas double passes ?

»
5 months 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"

»
5 months 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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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