C. Hasan and his lazy students

Codeforces

IDCF10216C

Time4000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length $N$, and they must tell him how many Longest Increasing Subsequences are in the array. For example, if the array is ($1$ $2$ $1$ $4$ $3$). The LIS's length is $3$, and it could be ($1$ $2$ $4$) or ($1$ $2$ $3$), so the answer is $2$. Note that you can't choose ($1$ $1$ $3$) because it must be a strictly increasing subsequence, and you can't choose ($1$ $2$ $3$ $4$) because you can't change the order of a subsequence. First line of the input will be $T$, number of test cases. Each test case starts with $N$, the size of the array, next line contain $N$ space separated integers, the array. $1 <= N <= 1000, 1 <= A_i <= 10^6$ For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $10^9 + 7$ ## Input First line of the input will be $T$, number of test cases.Each test case starts with $N$, the size of the array, next line contain $N$ space separated integers, the array.$1 <= N <= 1000, 1 <= A_i <= 10^6$ ## Output For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $10^9 + 7$ [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the length of the array. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be a sequence of integers with $ 1 \le a_{k,i} \le 10^6 $. **Constraints** 1. $ 1 \le T \le 100 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le n_k \le 1000 $ - $ 1 \le a_{k,i} \le 10^6 $ for all $ i \in \{1, \dots, n_k\} $ **Objective** For each test case $ k $, compute: - $ L_k $: the length of the Longest Increasing Subsequence (LIS) of $ A_k $, where the subsequence must be strictly increasing and preserve order. - $ C_k $: the number of distinct LISs of length $ L_k $ in $ A_k $, modulo $ 10^9 + 7 $. Output $ (L_k, C_k) $ for each test case.

API Response (JSON)

{
  "problem": {
    "name": "C. Hasan and his lazy students",
    "description": {
      "content": "Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of leng",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10216C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of leng...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the array.  \n- Let $ A_k = (...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments