Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Think of every cell as a graph node. A '<' has only one outgoing edge left, a '>' has only one outgoing edge right, and a '*' lets you choose either direction.
On a line, any directed cycle must contain two neighboring cells that can move into each other. There is no room for a fancy bigger cycle here; the river is one-dimensional, not a maze with delusions of grandeur.
Two adjacent cells form an infinite loop exactly when cell can move right and cell can move left. That means left char is either '>' or '*', and right char is either '<' or '*'.
If no such adjacent pair exists, then every finite trip is basically one-way until it hits the shore. A '*' is useful because from it you may choose the longer escaping direction.
With no infinite loop, compute escape times by DP: left-to-right for “time to leave if moving left from here”, right-to-left for “time to leave if moving right from here”. Then each cell’s best answer is its forced direction, or the max of both for '*'.
Key Idea
Model the river as a directed graph on a line.
From cell :
'<' forces you to ,'>' forces you to ,'*' lets you choose or ,So the problem is: can we choose a starting node and choices at '*' nodes to stay forever? If not, what is the longest path to outside?
When Is Infinite Sailing Possible?
Because movement is only between neighboring cells, any cycle must contain two adjacent cells that move into each other.
For adjacent cells and , we can loop forever if:
'>' or '*', and'<' or '*'.Then Monocarp can bounce between those two cells forever.
So if any adjacent pair satisfies:
(s_i \in \{'>', '*'} ) \quad \text{and} \quad (s_{i+1} \in \{'<', '*'}),print -1.
This covers examples like:
>< gives a forced bounce,>* can bounce because '*' can row left,*< can bounce because '*' can row right,** can obviously bounce.No need to search for giant cycles. On a line, a larger cycle would still require some adjacent “come back here” pair inside it. Physics remains annoyingly local.
If There Is No Infinite Loop
Now the graph has no cycles, so every possible journey eventually exits.
We need the maximum number of moves before leaving the strip.
Define two arrays:
For :
So:
Similarly for , computed right-to-left:
Once these arrays are known, the best trip starting at cell is:
Take the maximum over all .
Why The DP Is Safe
The only scary thing in this problem is revisiting cells forever. We already checked that and returned -1 if possible.
Without an adjacent pair that can move into each other, there is no directed cycle at all. Therefore every dependency in the DP eventually reaches an edge of the strip. The left DP and right DP are enough because movement is always to a neighbor; there is no teleportation, no hidden graph nonsense, no “maybe I should build Dijkstra” nonsense. Just count the longest escape path.
Complexity
For each test case:
Across all tests, the total length is at most , so this easily fits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = (int)s.size();
bool infinite = false;
for (int i = 0; i + 1 < n; i++) {
bool canRight = (s[i] == '>' || s[i] == '*');
bool canLeft = (s[i + 1] == '<' || s[i + 1] == '*');
if (canRight && canLeft) {
infinite = true;
break;
}
}
if (infinite) {
cout << -1 << '\n';
continue;
}
vector<int> L(n), R(n);
for (int i = 0; i < n; i++) {
if (i == 0) {
L[i] = 1;
} else if (s[i - 1] == '<') {
L[i] = 1 + L[i - 1];
} else if (s[i - 1] == '>') {
L[i] = 1 + R[i - 1];
} else {
L[i] = 1 + max(L[i - 1], R[i - 1]);
}
}
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) {
R[i] = 1;
} else if (s[i + 1] == '<') {
R[i] = 1 + L[i + 1];
} else if (s[i + 1] == '>') {
R[i] = 1 + R[i + 1];
} else {
R[i] = 1 + max(L[i + 1], R[i + 1]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '<') ans = max(ans, L[i]);
else if (s[i] == '>') ans = max(ans, R[i]);
else ans = max(ans, max(L[i], R[i]));
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = (int)s.size();
bool infinite = false;
for (int i = 0; i + 1 < n; i++) {
bool canRight = (s[i] == '>' || s[i] == '*');
bool canLeft = (s[i + 1] == '<' || s[i + 1] == '*');
if (canRight && canLeft) {
infinite = true;
break;
}
}
if (infinite) {
cout << -1 << '\n';
continue;
}
vector<int> L(n), R(n);
for (int i = 0; i < n; i++) {
if (i == 0) {
L[i] = 1;
} else if (s[i - 1] == '<') {
L[i] = 1 + L[i - 1];
} else if (s[i - 1] == '>') {
L[i] = 1 + R[i - 1];
} else {
L[i] = 1 + max(L[i - 1], R[i - 1]);
}
}
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) {
R[i] = 1;
} else if (s[i + 1] == '<') {
R[i] = 1 + L[i + 1];
} else if (s[i + 1] == '>') {
R[i] = 1 + R[i + 1];
} else {
R[i] = 1 + max(L[i + 1], R[i + 1]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '<') ans = max(ans, L[i]);
else if (s[i] == '>') ans = max(ans, R[i]);
else ans = max(ans, max(L[i], R[i]));
}
cout << ans << '\n';
}
}