Let's discuss problems. How to solve B and J?

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

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | antontrygubO_o | 173 |

Let's discuss problems. How to solve B and J?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/03/2021 08:01:46 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve M?

When N is odd, put N points around a circle, and choose all isosceles triangles.

When N is even,

Put N-1 points around a circle, and choose all isosceles triangles.

Add (the remaining point) — (i) — ((i+1)%N) for each 0 <= i < N.

Add (the remaining point) — (i) — ((i+2)%N) for each 0 <= i < N.

Remove extra triangles.

We should find proper coefficients but basically this is the idea of the answer.

Seems that you mixed up odd and even

What does equal number of trianges in your solution for odd and for even n?

If you are interested in details, here is my solution: http://ideone.com/o9GMsI

Got it.

What is test #3 in problem L ?

My team had the same problem. We mistakenly believed that the line of "e" can not get the string "egg". After fixing, we passed the test. Perhaps a similar case in the test 3. P.S. Sorry for my bad english

How to solve G?

Where can I find the final standings?

Division 1

Division 2

how to solve I?

We only need some edges. For every point we can reach this point from maximum 4 points(point J which has smallest Y, X[I] = X[J] and Y[J] > Y[I] and have direction 'D'.also for all other 3 direction). So we only have maximum 4 * N edges and now we can use simple dijkstra algorithm to get switch time of every robot. solution author LashaBukhnikashvili

How to solve D?

If someone is still interested in solution, it's dp[i][j] where i and j are the suffixes of the given permutations. If s1(i) != s2(j) then dp[i][j] = dp[i + 1][j] + dp[i][j + 1]. If s1(i) = s2(j) so let len be the length of the longest common prefix of these suffixes. Then we are in danger of counting some array twice untill one of our indices(i or j) has reached position i + len + 1. So let's say i will move to i + len + 1 before j will move to j + len + 1. Let's try every k so that we will go to the state dp[i + len + 1][len + k], k <= len. We need to count number of arrays that can be obtained from substring (i ... i + len) of the first permutation and from substring (j ... j + k — 1) of the second permutation. We will avoid double counting if we will not take number from the second permutation if we took less numbers from the first permutation. So it's equivalent to the number of bracket sequences with len opening brackets and k closing brackets. It can be precomputed by simple dp or using formula described in this comment http://codeforces.com/blog/entry/23266?#comment-276645. Then we have do the same for the index j. There are only O(n) such states.

Does anyone know how to solve problem J?

Pleade read about Prufer codes (that's a bit overkill, but a very nice one).

Thank you!

How to solve B?