Contest Results

(Analysis by Danny Mittal)

Define $D$ to be the maximum value of $\Delta_j$ over all queries $j$ and $S$ to be the maximum value of $T_i$ over all cities $i$.

Subtask 1: $D \leq 200$

By storing the sequence $c_{i, 0}, \ldots, c_{i, T_i - 1}$ as an array for each city $i$, we can calculate the next city Bessie will go to each day in constant time given the current day $t$ and her current city $i$ by looking at index $t \bmod T_i$ in the array for $i$.

This means that we can answer each query in $O(\Delta_j)$ time, making this solution $O(\sum T_i + QD)$, which is fast enough here.

Subtask 2: $N, \sum T_i \leq 2 \cdot 10^3$

Consider a situation where Bessie is currently at city $i$ on day $t$, and we know $i$ but only know $t \bmod S$. In order to figure out which city Bessie will go to next, we need to know $t$ modulo $T_i$. Crucially, because $T_i$ is a power of $2$ for all $i$, and $S$ is the maximum of all them, $S$ will also be a power of $2$ at least as large as $T_i$ and will therefore be a multiple of $T_i$. This means that given $t \bmod S$ we can simply mod by $T_i$ to get $t \bmod T_i$.

Thus, given $i$ and $t \bmod S$, we know exactly what city Bessie will go to next. This suggests constructing a directed graph whose nodes are pairs $(i, t)$ of a city $i$ and a day $t$ that we consider to be modulo $S$ (so in particular, there are only $S$ values of $t$). Each node has one outgoing edge pointing to another node (which makes this a functional graph, though we don't need to exploit this structure).

We now wish to be able to calculate which node we will get to if we follow the outgoing edge $\Delta$ times for large $\Delta$. To do this, we can use binary lifting (construct a table storing for each node which node we will get to if we follow the outgoing edge $2^k$ times for all $2^k \leq D$, then use this table to answer each query in $O(\log D)$).

There are $N \cdot S$ nodes, and for each one we calculate $O(\log D)$ entries, making the construction $O(NS\log D)$. Answering queries is then $O(Q\log D)$, making the overall runtime $O((NS + Q)\log D)$. $S$ is bounded by $\sum T_i$, and in this case is at most $2^{10}$, making this fast enough.

Java code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class InfiniteAdventureN2 {
    public static final int LG = 60;
    public static final int S = 1024;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        int[][] period = new int[n + 1][];
        tokenizer = new StringTokenizer(in.readLine());
        for (int city = 1; city <= n; city++) {
            period[city] = new int[Integer.parseInt(tokenizer.nextToken())];
        }
        for (int city = 1; city <= n; city++) {
            tokenizer = new StringTokenizer(in.readLine());
            for (int t = 0; t < period[city].length; t++) {
                period[city][t] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        int[][][] binaryLift = new int[n + 1][S][LG];
        for (int city = 1; city <= n; city++) {
            for (int t = 0; t < S; t++) {
                binaryLift[city][t][0] = period[city][t % period[city].length];
            }
        }

        for (int k = 1; k < LG; k++) {
            for (int city = 1; city <= n; city++) {
                for (int t = 0; t < S; t++) {
                    int halfwayCity = binaryLift[city][t][k - 1];
                    int halfwayT = (int) ((t + (1L << (k - 1))) % S);
                    binaryLift[city][t][k] = binaryLift[halfwayCity][halfwayT][k - 1];
                }
            }
        }

        StringBuilder out = new StringBuilder();
        for (int j = 0; j < q; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int currentCity = Integer.parseInt(tokenizer.nextToken());
            long currentDay = Long.parseLong(tokenizer.nextToken());
            long daysAdventured = Long.parseLong(tokenizer.nextToken());

            for (int k = LG - 1; k >= 0; k--) {
                if ((daysAdventured & (1L << k)) != 0L) {
                    int t = (int) (currentDay % S);
                    currentCity = binaryLift[currentCity][t][k];
                    currentDay += 1L << k;
                }
            }

            out.append(currentCity).append('\n');
        }
        System.out.print(out);
    }
}

Subtask 3: $N, \sum T_i \leq 10^4$

We want to do binary lifting like we did for Subtask 2, but a graph with $NS$ nodes would now be too large. Therefore, instead of considering pairs of the form $(i, t)$ where $t$ is modulo $S$ for all $i$, we will consider $t$ to be modulo $T_i$, so that the number of pairs is equal to $\sum T_i \leq 10^5$.

What goes wrong if we try to now just do binary lifting on these pairs? Consider a situation where we have two cities $a$ and $b$ such that $T_a < T_b$. Suppose that when Bessie is at city $a$ and the day is $t$ modulo $T_a$, Bessie goes next to city $b$. To calculate the binary lifting entry for Bessie going $2^1 = 2$ steps from $(a, t)$, we want to know where Bessie will go immediately after city $b$. However, we can't know this just from $t \bmod T_a$, because that doesn't determine $t \bmod T_b$.

This problem makes constructing a full binary lifting table impossible. To solve this, we will divide the cities into levels. At this point, there are two potential approaches:

Approach 1 (Level by $T_i$):

Each level contains all the cities with the same value of $T_i$.

For each city, we can at least construct the binary lifting table for that city up to the point where we reach a city of a higher level. If we also store the amount of days it takes for us to get to that first city of a higher level, then we can use the binary lifting table as follows:

To figure out where Bessie ends up if she starts at $(i, t)$ and adventures for $\Delta$ days, we repeatedly do the following:

If, starting from $(i, t)$ it takes at most $\Delta$ days to reach a city of a higher level, then go to that city.
Otherwise, find the highest power of $2$ at most $\Delta$ and use the binary lifting table to travel that many days.
Update $i, t, \Delta$ accordingly.

The second bullet point can be done at most $\lg D$ times, and because there are at most $\lg S$ levels, the first bullet point can be done at most $\lg S$ times in a row. This means that such a calculation takes $O(\lg D \lg S)$ time.

We can first construct the binary lifting table by going in order of increasing powers of $2$ and applying the above procedure to the existing entries (and also calculate when a higher level is reached where applicable), then use the same procedure to answer the queries. There are $\sum T_i \lfloor\lg D\rfloor$ entries and $Q$ queries, so the runtime complexity is

$$O\left(\left(\sum T_i\lg D + Q\right)\lg D \lg S\right)$$

which is fast enough.

Approach 2 (sqrt decomposition):

We will split the nodes into small and large nodes, where small nodes have $T_i \leq \sqrt S$ and large nodes have $T_i > \sqrt S$. For each large node $i$, we will compute the binary lifting table for all $(i, t)$, but for each small node we will only compute the binary lifting table for $(i, t)$ for $0\leq t < \sqrt S$ (i.e. for small nodes we only consider time mod $\sqrt S$). In addition, for each small node we will store the min. time required to reach a big node, and only store the $k$th entry of the $(i, t)$ table (corresponding to location after $2^k$ steps) if after $2^k$ steps we have never encountered a large node.

We can compute the small nodes in just $O(N\sqrt S \lg D)$, For large nodes, to compute the $k$th entry, we first refer to the $k-1$th entry. If this is a large node, we are immediately done, otherwise we jump to the next large node, and then recurse (roughly we are performing a query). This takes $O(\sum T_i\sqrt S \lg^2 D)$.

To do a query, we do the following, for $k = 60, 59, \ldots, 0$: If the next large node is within $\Delta$ away, jump to the next large node (and increment $t$ and decrement $\Delta$). Now, if $\Delta \geq 2^k$, jump to the next position in the binary lifting table (and modify $t$ and $\Delta$). This takes $O(\lg D)$ per query, so the total runtime is $O(\sum T_i \sqrt S \lg^2 D + Q\lg D)$.

Java code for the first approach:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class InfiniteAdventure {
    public static final int LG = 60;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        int[][] period = new int[n + 1][];
        tokenizer = new StringTokenizer(in.readLine());
        for (int city = 1; city <= n; city++) {
            period[city] = new int[Integer.parseInt(tokenizer.nextToken())];
        }
        for (int city = 1; city <= n; city++) {
            tokenizer = new StringTokenizer(in.readLine());
            for (int t = 0; t < period[city].length; t++) {
                period[city][t] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        int[][][] binaryLift = new int[n + 1][][];
        int[][] firstHigher = new int[n + 1][];
        long[][] firstHigherDays = new long[n + 1][];
        for (int a = 1; a <= n; a++) {
            binaryLift[a] = new int[period[a].length][LG];
            firstHigherDays[a] = new long[period[a].length];
            firstHigher[a] = new int[period[a].length];
            for (int k = 0; k < period[a].length; k++) {
                if (period[period[a][k]].length > period[a].length) {
                    firstHigherDays[a][k] = 1;
                    firstHigher[a][k] = period[a][k];
                } else {
                    binaryLift[a][k][0] = period[a][k];
                }
            }
        }

        for (int k = 1; k < LG; k++) {
            for (int city = 1; city <= n; city++) {
                for (int t = 0; t < period[city].length; t++) {
                    if (firstHigherDays[city][t] == 0) {
                        int laterCity = binaryLift[city][t][k - 1];
                        long remainingDays = 1L << (k - 1);
                        int e = k - 1;
                        long currentDay = ((long) t) + (1L << (k - 1));
                        while (remainingDays > 0 && period[laterCity].length <= period[city].length) {
                            while ((1L << e) > remainingDays) {
                                e--;
                            }
                            int laterT = (int) (currentDay % period[laterCity].length);
                            if (firstHigherDays[laterCity][laterT] != 0 && firstHigherDays[laterCity][laterT] <= (1L << e)) {
                                remainingDays -= firstHigherDays[laterCity][laterT];
                                currentDay += firstHigherDays[laterCity][laterT];
                                laterCity = firstHigher[laterCity][laterT];
                            } else {
                                remainingDays -= 1L << e;
                                currentDay += 1L << e;
                                laterCity = binaryLift[laterCity][laterT][e];
                            }
                        }
                        if (period[laterCity].length > period[city].length) {
                            firstHigherDays[city][t] = (1L << k) - remainingDays;
                            firstHigher[city][t] = laterCity;
                        } else {
                            binaryLift[city][t][k] = laterCity;
                        }
                    }
                }
            }
        }

        StringBuilder out = new StringBuilder();
        for (int j = 0; j < q; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int currentCity = Integer.parseInt(tokenizer.nextToken());
            long currentDay = Long.parseLong(tokenizer.nextToken());
            long remainingDays = Long.parseLong(tokenizer.nextToken());

            int k = LG - 1;

            while (remainingDays > 0) {
                while ((1L << k) > remainingDays) {
                    k--;
                }
                int t = (int) (currentDay % period[currentCity].length);
                if (firstHigherDays[currentCity][t] != 0 && firstHigherDays[currentCity][t] <= (1L << k)) {
                    remainingDays -= firstHigherDays[currentCity][t];
                    currentDay += firstHigherDays[currentCity][t];
                    currentCity = firstHigher[currentCity][t];
                } else {
                    remainingDays -= 1L << k;
                    currentDay += 1L << k;
                    currentCity = binaryLift[currentCity][t][k];
                }
            }

            out.append(currentCity).append('\n');
        }
        System.out.print(out);
    }
}

Full solution

The bottleneck in the first approach to Subtask 3 is the fact that the amount of entries in the binary lifting table is already $\log$ times linear, and we then have to spend $\log^2$ on calculating each entry. In a normal binary lifting table, calculation of each entry is constant because you just look at two existing entries.

So, we want to make our binary lifting table more like a normal one. To do this, we will construct a binary lifting table for each level instead: the $k$th entry for $(i, t)$ will, instead of telling you what city you will reach after $2^k$ days, tell you the $2^k$th city you will reach that is at the same level as $i$. This can then be computed in constant time using previous entries.

To construct the base of the binary lifting table, we will need to know for each pair $(i, t)$ what the soonest is that Bessie reaches a city $j$ at the same level as $i$ (and what $j$ is), in addition to the same for Bessie reaching a higher level.

If Bessie starts from $(i, t)$, let the first city she encounters of the same level be $f(i, t)$ and the first city she encounters of the same level $g(i, t)$. Before, we calculated $g(i, t)$ as part of the binary lifting construction, but now $f$ needs to be calculated beforehand, so we will calculate $f$ and $g$ together recursively:

From $(i, t)$, check what city $j$ Bessie will go to next.

If $j$ is at a higher level than $i$, then we know that $f(i, t)$ doesn't exist and $g(i, t) = j$.
If $j$ is at the same level as $i$, then we know that $f(i, t) = j$ and $g(i, t) = g(j, t + 1)$.
Otherwise, we can update $t$ and repeatedly compute $j = g(j, t)$ until we reach one of the first two situations, taking $O(\log S)$ time as there are $O(\log S)$ levels (note that we also need to store the number of days needed to reach $f(i, t)$ and $g(i, t)$).

This step thus takes $O(\sum T_i \log S)$ time.

Once those are calculated, we can calculate the binary lifting tables for each level, which will store not only the $2^k$th city in the same level that we get to but also the number of days needed to get there. The time taken is constant for each of the $O(\log D)$ entries per pair $(i, t)$, so $O(\sum T_i \log D)$ overall.

To answer a query, we take a greedy strategy similar to in Subtask 3. Keeping track of our current city i and current day t, as well as the day that Bessie stops:

While we have time to go to the next city with a higher level $g(i, t)$, we go there. This takes $O(\log S)$ steps.
Then, we use the binary lifting table to go as far as we can in our current level (note that for each $2^k \leq D$ instead of checking whether the number of days left to go is at least $2^k$, we need to check against the number of days needed to travel to $2^k$ cities in the same level, which we also stored in our table), which takes $O(\log D)$ steps.
If we have gone as far as possible in the current level and haven't finished Bessie's adventure yet, we go to the immediately next city (using $1$ day) and repeat the process from there.

Each iteration of this process takes $O(\log S + \log D)$ time, and each time we repeat it, after we increase our level as much as possible (the first bullet point) we end up at a lower level than last time, which means that we repeat the process at most $O(\log S)$ times. Thus, the entire calculation takes $O(\log S(\log S + \log D))$ time.

The overall runtime is therefore

$$O\left(\sum T_i \log S + \sum T_i\log D + Q\log S \left(\log S + \log D\right)\right) = O\left(\left(\sum T_i + Q\log S\right)\left(\log S + \log D\right)\right)$$

which is fast enough.

Java code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class InfiniteAdventure {
    public static final int LG = 60;
    public static final long LIMIT = 1_000_000_000_000_000_000L;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        int[][] period = new int[n + 1][];
        tokenizer = new StringTokenizer(in.readLine());
        for (int city = 1; city <= n; city++) {
            period[city] = new int[Integer.parseInt(tokenizer.nextToken())];
        }
        for (int city = 1; city <= n; city++) {
            tokenizer = new StringTokenizer(in.readLine());
            for (int t = 0; t < period[city].length; t++) {
                period[city][t] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        int[][] firstHigher = new int[n + 1][];
        long[][] firstHigherDays = new long[n + 1][];
        int[][][] binaryLift = new int[n + 1][][];
        long[][][] binaryLiftDays = new long[n + 1][][];


        for (int a = 1; a <= n; a++) {
            firstHigher[a] = new int[period[a].length];
            firstHigherDays[a] = new long[period[a].length];
            binaryLift[a] = new int[period[a].length][LG];
            binaryLiftDays[a] = new long[period[a].length][LG];
        }

        new Object() {
            boolean[][] seen = new boolean[n + 1][];

            void perform() {
                for (int a = 1; a <= n; a++) {
                    seen[a] = new boolean[period[a].length];
                }
                for (int a = 1; a <= n; a++) {
                    for (int k = 0; k < period[a].length; k++) {
                        calc(a, k);
                    }
                }
            }

            void calc(int city, int t) {
                if (!seen[city][t]) {
                    seen[city][t] = true;

                    int laterCity = period[city][t];
                    long days = 1;
                    while (laterCity != 0 && period[laterCity].length <= period[city].length) {
                        int laterT = (int) ((t + days) % period[laterCity].length);
                        calc(laterCity, laterT);
                        if (period[laterCity].length == period[city].length) {
                            binaryLift[city][t][0] = laterCity;
                            binaryLiftDays[city][t][0] = days;
                        }
                        days += firstHigherDays[laterCity][laterT];
                        laterCity = firstHigher[laterCity][laterT];
                    }
                    if (laterCity != 0) {
                        firstHigher[city][t] = laterCity;
                        firstHigherDays[city][t] = days;
                    }
                }
            }
        }.perform();

        for (int k = 1; k < LG; k++) {
            for (int city = 1; city <= n; city++) {
                for (int t = 0; t < period[city].length; t++) {
                    if (firstHigher[city][t] == 0 || firstHigherDays[city][t] > (1L << k)) {
                        int halfwayCity = binaryLift[city][t][k - 1];
                        if (halfwayCity != 0) {
                            int halfwayT = (int) ((t + binaryLiftDays[city][t][k - 1]) % period[city].length);
                            long days = binaryLiftDays[city][t][k - 1] + binaryLiftDays[halfwayCity][halfwayT][k - 1];
                            if (binaryLift[halfwayCity][halfwayT][k - 1] != 0 && days <= LIMIT) {
                                binaryLift[city][t][k] = binaryLift[halfwayCity][halfwayT][k - 1];
                                binaryLiftDays[city][t][k] = days;
                            }
                        }
                    }
                }
            }
        }

        StringBuilder out = new StringBuilder();
        for (int j = 0; j < q; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int currentCity = Integer.parseInt(tokenizer.nextToken());
            long currentDay = Long.parseLong(tokenizer.nextToken());
            long remainingDays = Long.parseLong(tokenizer.nextToken());

            while (remainingDays > 0) {
                while (true) {
                    int t = (int) (currentDay % period[currentCity].length);
                    if (firstHigher[currentCity][t] == 0 || remainingDays < firstHigherDays[currentCity][t]) {
                        break;
                    }
                    currentDay += firstHigherDays[currentCity][t];
                    remainingDays -= firstHigherDays[currentCity][t];
                    currentCity = firstHigher[currentCity][t];
                }

                for (int k = LG - 1; k >= 0; k--) {
                    int t = (int) (currentDay % period[currentCity].length);
                    if (binaryLift[currentCity][t][k] != 0 && remainingDays >= binaryLiftDays[currentCity][t][k]) {
                        currentDay += binaryLiftDays[currentCity][t][k];
                        remainingDays -= binaryLiftDays[currentCity][t][k];
                        currentCity = binaryLift[currentCity][t][k];
                    }
                }
                if (remainingDays > 0) {
                    int t = (int) (currentDay % period[currentCity].length);
                    currentDay++;
                    remainingDays--;
                    currentCity = period[currentCity][t];
                }
            }

            out.append(currentCity).append('\n');
        }
        System.out.print(out);
    }
}