Colorfulness of the squares
You have n square blocks arranged in a straight line. Every block has a number written on it. And each block has a color associated with it. A sub-sequence of blocks has "colorfulness" equal to the number of distinct colors in that sub-sequence.
An increasing sub-sequence is a sub-sequence of blocks where the numbers on the blocks are arranged in non-decreasing order.
You are given a q number of tasks as follows :
- In every task you will be given a number K.
- Consider all the increasing sub-sequences of length K in the given arrangement.
- Find and print the minimum "colorfulness" among all such sequences.
First line will contain n number of square blocks.
Next line contains n values each denoting the value written on the ith block in the line.(Ai)
Next line contains n values each denoting the color of the ith block in the line.(Ci)
Next line contain an integer q denoting the number of tasks.
Next q lines contain one integer each denoting K for that task.
For each task print the minimum colorfulness among all the increasing sub-sequences of length K. If there are no sub-sequences of length K then print -1.
- 1 <= n <= 2000
- 1 <= Ai <= 109
- 1 <= Ci <= 10
- 1 <= q <= 1000
- 1 <= K <= n
Input: 5 2 1 4 5 6 1 1 2 1 3 2 1 2 Output: 1 1All submissions for this problem are available.
|Tags||lis, npl_nitw, nplq1602, subset|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions