CHEFRRUN - Editorial

(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.)



Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Xellos






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.


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.


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.


The author’s solution can be found here.
The tester’s solution can be found here.


Hi I cannot view the solutions. I am getting access denied?

Hello ,access is denied to view the tester’s and author’s solution . Also if someone could see my solution and tell me where i went wrong :

Since the editorial solutions are not available at present, my Python 3.5 solution is:


for _ in range(int(input())):
    n = int(input())
    z = input().split()
    a = list(map(int, z[:n]))

    mag = []
    unused = [True]*n
    for ix in range(n):
        if unused[ix]:
            cyc = []
            c = ix
            while unused[c]:
                unused[c] = False
                c = (c + a[c] + 1)%n

            if c in cyc:
                mx = cyc.index(c)


strongly connected components. kosaraju algorithm

1 Like

can you tell how to apply kosaraju for this problem. plz do share code

@xellos0 @salman3007
Pls help Why im getting runtime error

@admin how can I access the author’s code, there is some technical error when I’m trying to access it. Thanks

My solution using Kosaraju’s Algorithm. For every strongly connected component, I have checked if there exists a cycle within it. If it does, then every member of that SCC must be included in our answer.