(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.
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;
}