### -emli-'s blog

By -emli-, 5 years ago, translation,

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.

• +18

 » 5 years ago, # |   0 Approaches for Task E : Grouping http://arc067.contest.atcoder.jp/tasks/arc067_c ?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +22 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, # |   0 How to solve F?
•  » » 5 years ago, # ^ |   +3 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// compute optimal values for ranges starting in [l..r-1], ending in [optL..optR] void calc(int l, int r, int optL, int optR){ int mi = (l+r)/2; // find the optimal range starting at mi int optM=optL; int curval=0; FORU(k, max(mi,optL), n-1) { // compute the value of the range [mi..k] int val = computeValue(mi,k); if(val > curval) { curval = val; optM = k; } } // the optimal end for mi is optM ans = max(ans, curval); if(l
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 what are the transitions for your DP before D&C optimization? Rafbill
•  » » 5 years ago, # ^ |   +3 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, # |   +13 Can the editorials be provided in English as well?
 » 5 years ago, # |   0 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, # ^ |   0 Can you share your approach for the O(N logN) approach?