# DCP-459: Square of Subsequence Back to All Problems

Medium Recursion > Backtracking with Pruning/Branch and Bound

You will be given an array of **N** elements. You have to partition two non-overlapping and non-empty subsequences such that the product of elements of first sub-sequences is **A**, and product of elements of second sub-sequences is **B**. Following conditions should meet, - A and B should be perfect square. - Position of last element of first sub-sequence should be less than position of first element of second sub-sequence, which is here Non-overlapping means. You have to **maximize** absolute difference between A and B. If it is not possible, print **-1**. Note: To know more about subsequence, see here: https://en.wikipedia.org/wiki/Subsequence Input: ------ First line of input will consist of an integer **T (T<=250)**, indicates the number of test cases follow. Each case starts with a line containing an integer **N, (1<=N<=15)**, indicates the length of array Arr. Next line contains **N** integers such that **1<=Arr[i]<=15**. Output: ------- For each test case you have to print the required answer. Sample Input ------------ 5 5 2 2 3 5 5 4 2 5 5 2 5 1 5 5 5 1 4 2 2 2 2 4 2 3 2 4 Sample Output ------------- 21 -1 24 0 0

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 21/192

Solve/Submission

### Ranking

# User Language Timing
01 rajdipsaha C 0.15s
02 emrul Cpp14 0.21s
03 sayedgkm Cpp14 0.22s
04 BishalG Cpp14 0.23s
05 mir003 Cpp 0.26s
06 feodorv C 0.28s
07 swapnil Cpp 0.32s
08 daihan_mbstu Cpp 0.34s
09 skmonir Cpp 0.37s
10 Taran Cpp14 0.51s
11 by_default Cpp 0.56s
12 khatribiru Cpp 0.60s
13 ssavi Cpp 0.61s
14 tariqiitju Cpp 0.63s