0
$\begingroup$

I am really confused with this problem.

Here's the problem:

You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at the same place, but multiple arrows can point to the same place and arrows can start and end in the same place. The arrow from place $i$ points to place $a[i-1]$,($a$ being an array representing the game board with $N$ elements and $i$ is between $1$ and $N$, inclusive).There are $0$ to $N$ tokens,inclusive, placed in those places and that, in each round, move along the arrows from their current place. If two or more tokens are in the same place, then you lose that game. But if that doesn't happen for the $K$ rounds specified, then you win the game. There may be multiple ways to solve the problem, but Two ways are different if there is some $i$ such that at the beginning of the game place $i$ did contain a token in one case but not in the other. Count those ways and return their count modulo $1,000,000,007$.

The whole problem is confusing to me, but what really confuses me is that it states that the arrow that starts from $i$ goes to $a[i-1]$. How I understand it, for the first example,( $\{1,2,3\} \;5$ Returns:$8$ ), if $a[1]=1$, $a[2]=2$, and $a[3]=3$, then $3$ maps to $2$ and $2$ maps to $1$, but then $1$ maps to $0$,(but point $0$ doesn't exist).

What would be more correct would be if $a[0]=1$, $a[1]=2$, and $a[2]=3$, but then all the points would map to themselves,(though it says in the example that the tokens don't move during the rounds).

I am probably way off, but I couldn't find many explanations, and the ones I found didn't make any sense to me, and I couldn't find many visual depictions either.

$\endgroup$
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Jun 25 '16 at 6:18
  • $\begingroup$ on a side note there exist detailed editorial for problems on topcoder, you might want to look up there first. $\endgroup$ – sashas Jun 25 '16 at 6:55
  • $\begingroup$ You're right, I did find an editorial, here: apps.topcoder.com/wiki/display/tc/TCO15+Round+1A. But the problem still persists, since it states that " a[j] means that in a given step all x tokens that existed in place j will be moved to a[j]-1". Through my understanding it would still mean that the arrow from point 1 would go to a non-existent point 0 or they wouldn't move at all. it is a good explanation, but I can't fully understand it considering it still doesn't really address my question. $\endgroup$ – Mr. Bombastic Jun 25 '16 at 15:51
  • 1
    $\begingroup$ What is the question? I see a copy-pasted problems and some thoughts on it, but no question we could answer. $\endgroup$ – Raphael Jun 26 '16 at 0:46
  • $\begingroup$ I'm confused on how all the points map to either themselves or there are 'n-1' arrows instead of n arrows. Like it states, 'i' maps to 'a[i-1]', so either point 1 doesn't have an arrow from it or they all just point to themselves. However, in this editorial: apps.topcoder.com/wiki/display/tc/TCO15+Round+1A and this mayokoex.hatenablog.com/entry/2015/04/12/085635, there are 3 arrows. In fact, in the second link, it shows 1 pointing back to 2. That is what really confuses me. $\endgroup$ – Mr. Bombastic Jun 26 '16 at 2:24
1
$\begingroup$

$a[0] = 1, a[1] = 2, a[2] = 3$.

"The arrow from place $i$ points to place $a[i−1]$"

So yes, all $3$ places in this sample point to themselves. It actually says in the explanation that "in each round each token will stay in the same place".

In the second sample, all three places point towards the first one.

In the third sample, you have a $2$-cycle: $1$ points to $2$ and vice-versa.

Is everything clear now?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I just wanted to make sure. Sorry if I was too bothersome. Thank you! $\endgroup$ – Mr. Bombastic Jun 26 '16 at 22:14
  • $\begingroup$ No problem, glad I could help! $\endgroup$ – Mihai Jun 27 '16 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.