vamaddur's blog

Can someone explain this solution to USACO 2013 Gold December Contest: The Bessie Shuffle?
By vamaddur, history, 7 years ago, In English

Click Here for Problem

Chinese Solution, since USACO does not have an official solution for the problem above.

I had a lot of trouble with the implementation of this question, so I looked up this solution online. Google Translate could only do so much for the page (the only solution I could find), but I think I was able to discern the following from the code:

1) The array "per" reverses the permutation process, and length of 31 represents a bitmask of that length,

2) The idea behind the "per" is that the result of a number of consecutive permutations can be assembled in logarithmic time, and

3) The variable "num" in the third main loop functions as a mask.

However, I do not fully understand the purpose of "bot", "now", and "k" in the third main loop, and the mathematics in the first and third main loops.

I would appreciate an explanation for these parts of the solution.

Thanks in advance!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Never mind.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I still have not been able to understand this problem, and I would appreciate the help.

Cheers!

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

hi there!

if you are still trying to understand that solution code then i'm sorry. i don't understand that voodoo code either.

However i solved the problem using a few observation and i can tell you about my idea.

If we build a directed graph by adding edge from each position to the position it ends up after a bessie shuffle ( that is add a directed edge from each i to p[i]-1 ) then observe how the graph would look like.

it would look like something like this:


node->node->node->0

node-->node--node
^            |
|____________|

node-->node
^        |
|________|

meaning, there will be some nodes connected to node 0 in like a SINGLE straight line and some other nodes forming a cycle in a circle form.

you can easily understand why this happens. it happens because every node has exactly one outer edge (except for 0 node) and since p[] array is a permutation of 1 to m, no two different nodes have outer edge to a common node. That is why the graph looks like that.

the nodes in the circle shape componant i.e. cycle will never get out of the deck. hence, number of such node can be atmost m-1 (irrelevant information)

now for each node you just have to find maximum number of bessie shuffle may be applied on this node. and find out where it may end up after this much travelling.

Now there is one more thing we can figure out, that node m will never be in a circle shape component i.e. a cylce. Because for that to happen for an i, p[i]=m+1 needs to be true but all p[i]<=m. so there will be path from m to node 0.

for any element > m , we can just think them as m.

for silver version of the problem (where n is lower) this much observation is enough.

for gold version, you need a little bit of more observation. for the gold version, we can just find out the position for the first m and last m element and see if there is a query asking for that position and if yes lets save the answer for that query. now if we have not figure out answer for a query in the end the answer for the node must be in m+1 to n-m-1 range. but this node will always getout of the deck. and with forming a simple formula we can find out the answer.

my code for silver version: https://pastebin.com/4hK8tPq6

my code for gold version: https://pastebin.com/Gnd3Pjgh

→ Reply