(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)

### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Sergey Kulik

**Editorialist:** Xellos

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

graphs

### PROBLEM:

There are N boxes in a circle. From box i, you can only move A_i+1 times clockwise. Count the starting boxes which you’ll reach again during such a walk.

### QUICK EXPLANATION:

You’re given a so-called functional graph; count the vertices which lie on cycles. Find all cycles by moving from each vertex over unvisited vertices, then move along each cycle to count them in linear time.

### EXPLANATION:

Let’s number the boxes 0 through N-1. Now, we can say that the boxes are vertices of a directed graph with exactly one outgoing edge from i to (i+A_i+1)\%N. This graph has a well-known property: if we move from any vertex along those edges, we’ll eventually encounter exactly one cycle and stay on it.

So let’s start in some vertex v_s and move along edges. If we encounter a vertex that was visited before (for some earlier starting vertex), we already visited the cycle that follows, so there’s nothing to do for that v_s. Otherwise, we’ll have to encounter a cycle that wasn’t visited before - as soon as we visit a vertex that was visited before, but for the current v_s, we can conclude that this vertex v_c lies on that new cycle. Then, it’s sufficient to move along this cycle until we get back to v_c and count the vertices visited on it.

After doing that for all v_s, all cycles had to be visited, so we’ve counted the number of vertices on cycles - th answer to our problem. Time and memory complexity: O(N), since we can’t visit any vertex more than twice this way.

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.