1200

Зеленый)

Как можно проследить, ТС в последнее время ощутимо теряет популярность.

I solved with DP. I think most, if not all of the greedy solution will fail.

You only need the "vertical or" operations on "HS" or "SH", because either horizontal operation can be replaced by one "vertical or" without changing the result.

I have a reduction to the "vertical or" operation only: if "HH" is adjacent to "SS", then it's optimal to "or" the "SS" with this "HH", if there's just "HS" or "SH" adjacent to a row of "SS"-s, then we can copy the column with H from either end without changing the answer. That's because each "SS" requires an operation of its own (so the first case is clearly optimal) and a "HS" or "SH" will be converted to "HH" in a "vertical or" operation, which the resulting row of "HS"/"SH" can be made part of. That also gets rid of "SS" columns.

The best course of action at this point isn't greedy, but DP, because it requires practically no thinking. For example, dp[k][i][j] tells you the smallest number of operations needed to convert states[k][i,j) into all "H"-s. The only interesting operations are "dp[k][i][j]+1->dp[1-k][i][j]" and "dp[k][i][l]+dp[k][l][j]->dp[k][i][j]" ("vertical or" operation and merging 2 substrings). In case you ask why I couldn't solve the problem this way, I'll let this pic say it:

I solved it greedy:

First eliminate every index where there is S in top and bottom row by expanding adjacent indexes which have a H with the third operator. It doesn't matter from which side you expand the non SS area.

Then forget every index which have H in top and bottom, and iterate over array and maintain the state HS or SH and count how many times state of HS turns into SH or SH turns into HS while iterating. Now there are count+1 areas. We can use operator 2 in every other of the areas and then use operator 2 into whole array.

You can do after competition is over on Topcoder site by clicking on your last match in profile and clicking on details before that I don't think you could.

Another common mistake in d1 250 was to iterate up to N^1/2 after dividing N by all given primes, which is slow for cases N = 2*P, P — huge prime.

Why should the cube root be considered?

Primes up to can be found easily and so can the quotient after dividing by them as much as possible. There are at most 2 prime divisors (not necessarily distinct) greater than and the quotient we got is their product.

If there are 2 of them, we have to be told one (because they're the largest divisors) and finding the other is trivial.

Alternatively (and that's how I solved it): we have the time to check primes up to , same for all given primes; if there's anything left, then we can't factorise it in time, so it has to be a prime :D