This just popped up after more than 2 month pause of contests. The round is scheduled at 15:00 UTC May 22, 2023.

Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

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

1 | jiangly | 3640 |

2 | Benq | 3593 |

3 | tourist | 3572 |

4 | orzdevinwang | 3561 |

5 | cnnfls_csy | 3539 |

6 | ecnerwala | 3534 |

7 | Radewoosh | 3532 |

8 | gyh20 | 3447 |

9 | Rebelz | 3409 |

10 | Geothermal | 3408 |

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

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 158 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 151 |

8 | SecondThread | 147 |

9 | orz | 146 |

10 | pajenegod | 145 |

I just saw vanhanh.pham in top 5 of round 271 and remembered that he won another Div 2 round in the past. Then I found his performances quite "interesting". You may want to check his submissions in Div 1 rounds.

Although it is completely legal to do this, intentionally (I really hope that someone can prove me wrong) dropping rating to participate in Div 2 rounds officially is such a shameful behavior. I'm pretty sure I know his real handle and he has no trouble with staying in Div 1 (became red). How does he not know about unofficial participation in Div 2 rounds? * sarcasm *

Recently, this problem was given in my algorithm class:

"Given an undirected graph G = (V, E). We want to remove some edges such that all biconnected components in G does not change (specifically, "change" here refers to set of vertices). Find a way of removing maximum number of edges."

We can see that for cases in which a component consists of a Hamiltonian cycle, the problem becomes finding the Hamiltonian cycle and remove all other edges in that component. This is a NP-Complete problem. So, is it possible conclude that the original problem is also NP-Complete?

It seems that some people haven't got the idea of this problem 285E - Positions in Permutations while the tutorial is still incomplete so I'd like to write some explanations about it.

A common approach for this kind of problem is DP. What we do here is to choose numbers for the good positions first, then fill the others later on. Let `f(i, j, k)`

is the number of ways to choose j good positions in the first i-th position and k is a 2-bit number that represents whether number i and number i + 1 is already used or not. The DP transition is quite simple.

Let `F(j)`

is the number of permutations with j good positions, then `F(j) = Σ(f(n, j, k)) * (n - j)!`

(because there are n — j numbers left unchosen). However, there are cases we may form some extra good positions when putting these n — j numbers into our permutations, thus `F(j)`

now stores the number of permutations with **at least** j good positions. But we want `F(j)`

to be the number of permutations with **exact** j good positions, so we must exclude those permutations with more than j good positions.

Let's do it in descending order. First `F(n)`

must be the number of permutations with exact n good positions. Hence, we may calculate `F(n - 1)`

based on `F(n)`

, then `F(n - 2)`

based on `F(n - 1)`

and `F(n)`

, and so on... The last part is to calculate how many times `F(j)`

is repeatedly counted in `F(i)`

(i < j), it's simply `C(j, i)`

(the number of ways to choose i good positions from j good positions).

The overall complexity is O(n^2).

Please refer to my submission 3376355 for an implementation.

When I try to enter UVA, Firefox shows a message: "Firefox has detected that the server is redirecting the request for this address in a way that will never complete. This problem can sometimes be caused by disabling or refusing to accept cookies." (Chrome doesn't work either)

Then I disable cookies from it and enter, but this way prevent me from logging in. Anybody knows how to fix this problem?

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/24/2024 09:33:32 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|