kostka's blog

By kostka, 18 months ago, In English

Round F starts in less than an hour! See you on the scoreboard!

http://goo.gle/KS-2022-F

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

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

Good luck everyone!

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

Runtime Error on Test Set 1 of problem B when I would have passed Test Set 2, because N is bigger for Test Set 1. Damn.

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

Could have got 12 more points if I had 2 more minutes.

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

In D2, I used some algorithm for the first time I don't even know to get AC. The trick basically updates the sum of first $$$k$$$ people's cancelled meetings from an ordered set of $$$n$$$ people (sorted by count of cancelled meetings).

Can anybody quote the algorithm? Or is it just a random one?

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

    Are you challenging us to guess what you did, or are you asking us whether what you did has a formal name?

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

      Yeah, I am actually interested in the formal name for what I did. Apologies that I didn't quoted my submission.

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

        Looks like you're using the kth order statistic feature of ordered set, a policy based data structure based on red-black trees.

        I'm not aware of a formal name for what you're doing here; just that you are using the features of the data structure.

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

The second problem had a natural problem statement, however as obvious as it may seem to lot of readers, authors should specify enviroment variables such as the bottomost container indicates it is kept on surface of some body with gravity because the principle linked in editorial only works with certain conditions IIRC(bottom level is closer to the body exhibiting gravitation force on water, there is gravitational force). The problem also incentivisted people who have studied a little bit about fluid mechanics and seen this experiment.

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

    When I read the statement I initally thought this was unclear too. One of the examples does clear up any ambiguity, but I agree that it should be in the statement.

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

The constraints on B were evil. I just looked at test set 2 and got a Runtime error because of it.

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

Problem C (Story of Seasons) Test Set 1 is very similar to this AtCoder problem: ABC137d

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

Can anybody help me figure out why I am getting a wrong answer on test 2 in Problem C !!

The link for the submission is https://pastebin.com/x5hSZaPp.

Please help !! Thanks in advance :)

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

    I was getting TLE from the debug lines (I guess Google doesn't have ONLINE_JUDGE defined), and then there's a small mistake. Maybe this test case can help you find it?

    Спойлер

    (the solution)

    Спойлер