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

PROBLEM LINK:

Practice
Contest

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.

Tester's solution
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 100000 + 10;

int a[MAXN], tag[MAXN], w[MAXN];

int main () {
    int sumN = 0;
	int testCases;
	cin >> testCases;
	while (testCases--) {
		int n;
		cin >> n;
        sumN += n;
        assert(1 <= n && n <= 100000);
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
            assert(0 <= a[i] && a[i] <= 1000000000);
			a[i] = (i + a[i] + 1) % n;
			if (a[i] == 0)
				a[i] = n;
			tag[i] = 0;
		}
		for(int i = 1; i <= n; i++)
			if (tag[i] == 0) {
				int pos = i;
				int wn = 0;
				while (!tag[pos]) {
					w[++wn] = pos;
					tag[pos] = 3;
					pos = a[pos];
				}
				if (tag[pos] <= 2) {
					for(int i = 1; i <= wn; i++)
						tag[w[i]] = 1;
				} else {
					int currentTag = 1;
					for(int i = 1; i <= wn; i++) {
						if (w[i] == pos)
							currentTag = 2;
						tag[w[i]] = currentTag;
					}
				}
			}
		int ret = 0;
		for(int i = 1; i <= n; i++)
			ret += (tag[i] == 2);
		cout << ret << endl;
	}
    assert(1 <= sumN && sumN <= 1000000);
	return 0;
}

RELATED PROBLEMS:

1 Like

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 : https://www.codechef.com/viewsolution/18711836

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

# https://www.codechef.com/problems/CHEFRRUN

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]:
                cyc.append(c)
                unused[c] = False
                c = (c + a[c] + 1)%n

            if c in cyc:
                mx = cyc.index(c)
                mag.extend(cyc[mx:])

    print(len(mag))

strongly connected components. kosaraju algorithm

2 Likes

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

@xellos0 @salman3007
Pls help Why im getting runtime error
https://www.codechef.com/viewsolution/34057781

@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.
https://www.codechef.com/viewsolution/38296279

1 Like

2 Likes

getting TLE in 16th test case of subtask 2, please help

https://www.codechef.com/viewsolution/44382530

why I am getting TLE ? my solution is similar to the explaination above.
https://www.codechef.com/viewsolution/46645406

The author’s and tester’s code isn’t accessible, how can I get access to those?

@archit_bikram - we have added the tester’s code to the original editorial post. You should be able to access it there.