AtCoder Grand Contest 028 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

# | User | Rating |
---|---|---|

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Petr | 3161 |

4 | LHiC | 3158 |

5 | CongLingDanPaiSh…5 | 3116 |

6 | ko_osaga | 3115 |

7 | mnbvmar | 3111 |

8 | Um_nik | 3104 |

9 | Benq | 3098 |

10 | Swistakk | 3089 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | Errichto | 163 |

3 | rng_58 | 161 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Swistakk | 149 |

7 | Petr | 149 |

9 | PikMike | 148 |

10 | 300iq | 147 |

AtCoder Grand Contest 028 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2018 14:17:49 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

3min

F is solvable in

O(N^{2}logN), so please try it.My solution is slower than most of the

O(N^{3}) solutions:(my implemention

Is there any way to distinguish them?

I have solved task A and I have read 'editorial', but could anyone explain the solution in his own words?

How to solve task B?

Basic idea is this: fix two specific elements

iandj. The cost for removing blockjwill include the weight ofiif and only ifjis removed first out of the blocks in the sectionithroughj. If not,iwill be disconnected fromj(or won't be present at all) by the timejis removed.The number of permutations in which

jis removed first among the blocks inithroughjisN! / (j—i+ 1). That's because there'sN! total permutations, there arej—i+ 1 blocks in that section, and by symmetry each of the blocks appears first in the same number of permutations.By precomputing

N! /kwe get anO(N^{2}) solution. It can be sped up toO(N); maybe you can see how.Thank you very much :)

Here, two blocks x and y ( x ≤ y ) are connected when, for all z ( x ≤ z ≤ y ), Block z is still not removed. Does it mean only blocks to the left of y are connected to it ? Can someone explain the connectivity of two blocks? or all blocks which are not removed are connected ?

Connectivity is reflexive. By “x and y are connected” they mean “x and y are both connected to each other.”

Does it imply all blocks which are not removed are connected ?

No, the condition for x, y (x <= y) to be connected is that all blocks z in the interval [x, y] should not have been removed yet. If you have three blocks 1, 2, 3 and 2 is removed, then 1 and 3 are no longer connected.

Got it. Thank you !!

Can someone explain how to solve problem B ? I'm not getting it through editorial.

It seems that F1 is solvable in

O(N^4/w)with bitset and some optimizations, for example this submission.Can someone explain the solution to task B?