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 Setter:

Bir Bahadur Khatri

Please login to submit solution to this problem.

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

Problem Stats

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
15 adamantium Cpp 0.71s
16 hrOarr Cpp 0.91s
17 SakibAlamin Cpp14 0.98s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support