How should I practice Maximum Signal Walk in a Server Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tower Research Capital online assessment problems in FastPrep.

Is Maximum Signal Walk in a Server Tree associated with Tower Research Capital?

FastPrep tags this as a Tower Research Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Maximum Signal Walk in a Server Tree

Tower Research Capital● HardNEW GRADOA

Problem statement

A network of n trading servers, numbered 0 to n - 1, forms a rooted tree. Server 0 is the root, the primary trading engine. For every other server i, parent[i] is the server directly above it, and parent[0] = -1. Each server i has a nonzero signal value signals[i].

A walk starts at any server, moves along tree edges between a server and its parent in either direction, and stops at any server. A walk may visit the same server many times. Keep a number Y that starts at 1. The first time the walk visits a server v, including the server where the walk starts, update Y:

If signals[v] > 0, set Y = Y * 2^signals[v].
If signals[v] < 0, set Y = -1 * Y * 2^(-signals[v]).

Later visits to a server do not change Y.

Find the largest value of Y that any walk can produce. Compare the real values of Y, not their remainders. Return that largest Y modulo 998244353, as a number from 0 to 998244352. If the largest Y is negative, return (Y mod 998244353 + 998244353) mod 998244353.

Function

maxSignalWalk(parent: int[], signals: int[]) → int

Examples

Example 1

parent = [-1,0,0,1,1]signals = [30,-2,4,-1,5]return = 780136139

Server 0 has children 1 and 2, and server 1 has children 3 and 4. The walk 3 → 1 → 4 → 1 → 0 → 2 visits every server. It passes server 1 twice, but only the first visit counts.

Two signals are negative, so the two sign flips cancel and Y = 2^(30 + 2 + 4 + 1 + 5) = 2^42 = 4398046511104. No walk can do better, because visiting every server already uses every factor and gives a positive result.

4398046511104 modulo 998244353 is 780136139.

Example 2

parent = [-1,4,1,1,0]signals = [2,-3,1,-4,-5]return = 2048

Server 0 has child 4, server 4 has child 1, and server 1 has children 2 and 3.

Visiting all five servers brings in three negative signals, from servers 1, 3, and 4, so Y would be -2^15. A positive Y needs an even number of negative servers.

The walk 0 → 4 → 1 → 2 skips only server 3. It has two negative signals, so Y = 2^(2 + 5 + 3 + 1) = 2^11 = 2048. Any walk that visits a different set of servers with an even number of negative servers gives at most 2^10 = 1024, for example the walk 0 → 4 → 1.

Example 3

parent = [-1]signals = [-3]return = 998244345

There is only one server, so every walk visits just server 0. Its signal is negative, so Y = -1 * 1 * 2^3 = -8.

The largest Y is -8, and (-8 mod 998244353 + 998244353) mod 998244353 = 998244345.

Constraints

1 <= n <= 10^5
parent.length == signals.length == n
parent[0] == -1, and 0 <= parent[i] <= n - 1 for every i >= 1
The parent array describes one tree rooted at server 0.
-10^9 <= signals[i] <= 10^9
signals[i] != 0