Problem statement: The Sultan had a permutation of numbers from 1 to N. For interest, he put inequality signs ">" and "<" between adjacent permutation numbers. For example, if the permutation was [1, 3, 2, 5, 4], then it would be [1<3>2<5>4]. He got tired of playing with his swap and went to make himself a mango smoothie. While the Sultan was preparing a smoothie, his cat entered the room and erased all the numbers, but the inequality signs remained. Now the Sultan is interested in how many permutations exist that satisfy these inequalities. Since there can be many ways, he asked you to help him and give an answer modulo 998244353. __
A permutation of numbers of length N is an array of N integers, where each number from 1 to N occurs exactly 1 time. For example, [1 2 3] and [4 2 1 3] are permutations, but [1 2 2] and [1 2 3 5] are not. __
Input The first line contains an integer N — the length of the permutation. The second line contains a string of N-1 characters "<" or ">".
Output Print the number of permutations modulo 998244353.
So there some subtasks
n<=10 — 10 points
n<=20 — 10 points
n<=500 — 30 points
n<=2000 — 60 points
Examples:
Input
5
<><<
Output
9
Input
3
<>
Output
2
I already have idea for first subtask using n! solution
Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).
Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).
Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).
Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).
Just a wonder, where does come this problem ?
From Kazakhstan olympiad
Actually, you can find the problem in atcoder dp contest.
We can solve the first case by trying all permutations — 10! * 10 = 40m is doable.
We can solve the second case using dp and an optimization: Our DP state is (location, the last number, the list of numbers remaining to place) and we recurse by trying all remaining numbers. This gives 20 * 20 * 2^20 = 400m might be just doable with some good constants, depending on constraints.
Pushing further relies on an observation:
Consider the structure of the remaining numbers. Regardless of what numbers we've removed, the order remains the same. i.e. the state (1<, 3,6,8) is equivalent to (1<, 2,4,5). With this in hand, we can simplify our DP state — Instead of keeping a bitset or list of what numbers remain, just keep a count of how many match the most recent criteria. Now our DP state is (location, # of choices) and we go through # choices child states to solve, which brings us down to N^3, which solves test case 3, but maybe not 4.
To solve 4, take a further observation: our choices at each place form a similar structure (1 choice, 2 choice, 3 choice, up to x choices). Instead of redoing that sum each time, let's keep a cumulative sum of (choices 1..x) as an addition to our DP. This might double our states, but reduces the number of choices we have to make at each step from N down to 2, giving us a total N^2 time solution.
lol
about the solution for the second case.
Doesn't such dynamics require 2 ^ 20 * 20 * 20 memory, or am I misunderstanding something?
Naively. If 400mb is too large, you can do the DP bottom-up in a row-based fashion to reduce it.
The 3 and 4 solutions also work, so I wasn't worried about getting 2 exactly right. There might be something I missed that solves 2 but not 3.