BallBreaker's blog

By BallBreaker, history, 2 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BallBreaker (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a wonder, where does come this problem ?

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

The observation
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    lol

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    about the solution for the second case.

    Doesn't such dynamics require 2 ^ 20 * 20 * 20 memory, or am I misunderstanding something?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.