Problem Help? Exercise Gold

Problems and Contests
#1

Hello USACO Guide Forum!

Here’s the problem I’m referring to: http://usaco.org/index.php?page=viewproblem2&cpid=1043

Uh, I pretty much have 0 idea of what to do? How am I supposed to approach this problem? I glanced over the editorial but it wasn’t very helpful on where to start, other than the fact this has some relationship with Permutations…

I don’t even know anymore: I’ve been stuck on this for 3 weeks now.

Best,
ShiftyBlock

#2

What do you mean by “glanced over”? The first sentence of the editorial might be a reasonable place to start:

Hint

Call the number of steps that a permutation takes the period of the permutation. Every permutation can be partitioned into cycles of sizes c_1,c_2,c_3,…,c_k such that c_1+c_2+…+c_k=N (see Swapity Swapity Swap from the last contest). Then the period is equal to lcm(c_1,c_2,…,c_k).

#3

Hi! I think to solve this you need to know some stuff about permutations (or how to use OEIS, oops).

The main thing you should know is that the order of a permutation is the LCM of the cycle lengths. Try to figure it out from there, or if you need more help, read the editorial.

Also, this problem is really similar to POI 2004 Maximal (with some other details) so you should try it out after you solve this to make sure you really understand!

1 Like
#4

tyty
also, very helpful to know that “order of a permutation is the LCM of the cycle lengths”. Was 100% unaware of this, at all.

#5

I glanced over the editorial but it wasn’t very helpful on where to start, other than the fact this has some relationship with Permutations…

also, very helpful to know that “order of a permutation is the LCM of the cycle lengths”. Was 100% unaware of this, at all.

Someone didn’t read the first line of the analysis :wink:

#6

the first line of the analysis is scary… how did you even come up with that

Okay, for clarification, I was very stuck on the reasoning behind the order of a permutation is the LCM of cycle lengths. The analysis tells it but it’s up to me to figure that out, which is kind of why I mentally quit.

But good to know that I probably shouldn’t mentally quit… oops.

#7

Anywhere I can find a submission place for Java? For the POI problem you are talking about?

#8

If szkopul doesn’t support Java submissions I don’t really know of any other place.