Candies :
Difficulty Level : Medium
Submissions : 55
Asked In :
Marks :100
: 0 | : 0
Alice and his friend Bob love candies so they have stored the N and M candies in an array of type $$$a_i$$$, $$$a_{i+1}$$$ ..... $$$a_{n-1}$$$.and $$$b_i$$$, $$$b_{i+1}$$$ ..... $$$b_{m-1}$$$. where $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i \le b_i \le 10^3$$$) stored the candy type that Alice and bob had. Bob, didn't store as many candies as Alice when he got some candy he eat them. Now Bob wants to eat one candy from his leftmost collection of the array $$$b$$$ but he wants to know if he eats any $$$b_i$$$ candy from the array $$$b$$$ after that is there in any permutation of the subarray that his sister had if yes store all the starting index of all such permutation. Bob wants all the indexes of such permutation of the subarray that his sister had in ascending order for all his candies type bob had.
It is given that N is always greater equal to M.
A subarray is a continuous part of the array and permutation of elements in the rearrangement of elements of an array
The first line of the test case contains two integers N and M ($$$1 \le M \le N \le 2*10^3$$$) — the number of chemical reactions Ram and Shyam had.
The second line of each test case contains N integers $$$a_i$$$, $$$a_{i+1}$$$ ..... $$$a_{n-1}$$$ ($$$0 \le a_i \le 10^3$$$) — the ph value of the items.
The last line of each test case contains M integers $$$b_i$$$, $$$b_{i+1}$$$ ..... $$$b_{m-1}$$$ ($$$0 \le a_i \le 10^3$$$) — the ph value of the items.
For each test case, print a line containing space-separated starting indices of Alice's subarray, which matched Bob's candies array in ascending order, and if no match is found, -1 should be printed.
5 3 1 2 2 1 1 1 2 1
1 3 4
5 3 1 2 3 4 5 6 7 8
-1
Example for Better Understanding :
N = 5 , M=3
A = [ 1 , 2 , 2 , 1 , 1 ]
B = [ 1 , 2 , 1 ]
•When you delete the 1st element from B, it becomes [ 2 , 1 ]. You can see in array A the subarray of length 2 starting for index 1 is [ 1, 2 ] and as [ 1, 2 ] is the permutation of [ 2 , 1 ], you have a match corresponding to this subarray. Similarly, the subarray starting at index 3 is also a match. So you get 2 matches corresponding to index 1 and index 3. Now the array B is restored , B = [ 1 , 2 , 1 ]
• Now when you delete the 2nd element from B, it becomes [ 1, 1 ]. For this, you can find 1 match corresponding to the subarray starting from index 4 .
•Removing 3rd element is of no use as we had already removed 1 before and checked for it .
• Therefore, the corresponding indexes are [ 1 , 3, 4 ].
