-emli-'s blog

By -emli-, 5 years ago, translation, In English

Hello everyone!

Today 15:00 MSK will be held personal competition.

AtCoder Regular Contest 067

AtCoder Beginner Contest 052

I invite everyone to participate and let's discuss problems after the contest.

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

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

Approaches for Task E : Grouping http://arc067.contest.atcoder.jp/tasks/arc067_c ?

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it +22 Vote: I do not like it

    denotes number of ways of putting people in groups of size . where denotes number of ways to distribute people in groups of size .

    .
    Answer is .

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

How to solve F?

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

    First observation : a solution will visit a range of restaurants, pick the best meal for each ticket in the range, and pay the distance from the start to the end of the range.

    It is possible to compute the optimal solution for a range in O(m) time using m range maximum queries and subtracting the distance. This gives a O(n^2 m) algorithm. It is possible to improve it to O(m n log(n)) with divide and conquer optimization.

    Code for D&D optimization :

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

    Let's for each pair (restaurant; ticket number) find all segments of restaurants, on which this pair will be used. To do so we can use standard algorithm with stack, to find nearest restaurants with better meals for this tickets. Let's call position of our restaurant pos, and these two restaurants rightPos and leftPos. Our pair will be used on segments with left border [leftPos + 1;pos], and right position [pos;rightPos - 1]. To find values for each segment we can just add value of all pairs in correspounding rectangles in [leftPos;rightPos] plane. It will work in O(n2 + nm)

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

Can the editorials be provided in English as well?

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

Problem C was very good, and I can solve it for O(N log N). Is there more efficient algorithm like O(sqrt(N))?

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

    Can you share your approach for the O(N logN) approach?