ABalobanov's blog

By ABalobanov, history, 12 months ago, In English

Hi to everyone! I decided to create a blog with some problem which was invented by me several years ago and only simple version of it was used in municipal stage of all-russian school olympiad in Kaliningrad. I wanted to use it somewhere but now I understand that it is not possible anymore because very very similar problem with similar ideas was used in codeforces round 858(it was f1-f2). I should have used it earlier somewhere and it is my second time that I lost my problem(first was div2 C from some old round). Now I just post it here so feel free to solve it and post your solutions. Later I can write my solution. Warning: if you haven't participated in round 858 and want to do it virtually or just solve problems from there then I advice you not to read it because you may get spoilers.

Problem
  • Vote: I like it
  • +16
  • Vote: I do not like it

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

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

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

For me the first part (figuring out how to solve the problem with $$$k = 2$$$) was slightly more difficult rather than generalizing it for bigger $$$k$$$'s.

Here is the solution:

Solution for k = 2
Solution for k = 1..n
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Congrats! My idea was the same. About complexity: I started to work on this problem and had testcases where $$$O(Nlog^2C)$$$ was too much. There is $$$N(log N+log C)$$$ solution

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Hmm, probably one can

      Spoiler

      Nice problem, by the way!

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

        Thanks! Yes my idea of lowering the complexity is also the same.

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

        How do you think was I right publishing it now or it could still be used as it have slightly different statement and maybe (only) one of observations.