so registration starts five minutes before round, right?

You know what is unnecessary? Spam comments. (as in: comments that are unrelated to the topic of the blog post)

When spam appears, downvotes are necessary.

Perhaps you'd better ask in this TC forum thread.

Yes. It's for everyone.

Yes it is.

Hacking round (Challenge phase) starts five minutes after coding phase and lasts 15 minutes.

I did, yes. I just tried to register.

You get a bye to Round 2, you don't need to participate in Round 1 ;)

http://apps.topcoder.com/forums/?module=Thread&threadID=852308&start=0&mc=7#2004386

Применили указанную операцию К раз при помощи бинарного возведения в степень. Посмотрели, что во что перешло: клетки разбились на классы эквивалентных. Ответ — произведение (размер_класса_i + 1).

Заметим, что если какие-то два токена оказались в одной позиции, то сколько бы раундов мы не делали, они будут все время находиться на одной позиции. Для каждой стартовой позиции токена промоделируем min(100, K) раундов и запомним, в какой клетке остановился токен. Если на какой-то клетке в итоге остановилось несколько токенов, значит изначально (чтобы не проиграть) мы могли выбрать только один из них (или ни одного). Соответственно, для всех конечных позиций перемножим количество остановившихся на них токенов + 1.

Hall's theorem. Then just check every subset of one side of the graph.

Another keyword is a constricted set.

If the range is long enough (10^10 is plenty), the answer is 10. Otherwise use brute force. This is an O(1) solution for the general case. Does that count as "cool"? :)

Oh okay, 10^20 is a lot. Instead you can construct all reachable sets of digits like this: go from the left to the right, remember the set of digits you already used, and whether you match the prefix of L so far, the prefix of R so far, or are already somewhere inbetween. (In the first two cases the set of digits you can use next is restricted.) Then do the less-brute force step in (2^10)^2 to find the best solution. (Disclaimer: I haven't tried actually implementing it.)

cannot prove it, but my thought is like this:

for each bitmask 0 ... 2^10-1 (representing digits) find the smallest number in [L, R] that has the corresponding digits. find next number with those digits (and that is not next_permutation) and check if it is in [L, R].

Why 100, I tried with 9 in the contest. The logic was to swap last two digits and get all the matched characters. There are many flaws in that. Can you prove why 100 is sufficient?

Here is my idea (passed)

first , given two numbers how can i find their similarity?

Assign to both number a list of 10 bits , (bit number i is one if the digit appears at least once in the given number otherwise its 0) ;

One can see that this list can be stored using an integer <2^10 using binary representation;

Now you just iterate from L to R and for each number you brute-force (using backtracking) any combination of its digits (one number can have at most 5 digits) and then you check whether the resulting bit-mask has appeared before in some past value.

Notice that if two tokens are ever on the same square, they will continue to be on the same square for the remaining turns, so a sufficient and necessary condition for two tokens to be on different squares after any of 1, 2, ..., K turns is for them to be on different squares after K turns.

Then, find, for each square s, where a token on that square would be after K turns. Call this square out(s). For a set a₁, a₂, ..., a_i of squares such that out(a_i) = s for all i, at most one of them can have a token, so multiply the final answer by i + 1. Do this for all s to finish.

One implementation detail is to find out(s) without doing a dfs of depth K ≤ 10⁹. You can note that there must be a cycle after at most N turns. From here, either do something like K = min(K, N + 1) or do cycle detection (keep track of last_visited for each square).