flashmt's blog

By flashmt, 6 years ago,

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 *

• +78

By flashmt, 7 years ago,

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?

• +11

By flashmt, 8 years ago,

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.

• +70

By flashmt, 8 years ago,

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?