2015年5月4日月曜日

VK Cup 2015 - Round 3 : C. Idempotent functions

Problem:

http://codeforces.com/problemset/problem/542/C

Algorithm:

Given some x and do below for many times:
 x <- f(x)
Observe the transition of x and find out that there is loop.(the shape is like "ρ")
For example, suppose n=6 and f is
f : i -> i+1 (i=1,2,3,4,5)
   6 -> 3
and when x=1, then
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ...
and the loop is 3->4->5->6 -> ...
also, if we start with x=5, then
5 -> 6 -> 3 -> 4 -> ...

when x is in the loop, then x moves only in the loop. So, let k is the length of loop(in this example, k=4) and m is some multiples of k, f^m(x) moves x to x(if x is in the loop).
For x that is not in the loop will go to loop for big k. Let s is minimum number of step that is needed to go to loop for all x.(in this example, 2 steps needed to go loop and s=2), then f^(m+s)(x) moves all points to loop. and this is Idempotent.

And we must be carefull that there is some "ρ".
So, we need s to be the longest "stick" and m to be the LCM of length of loops.

0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...