help plz - Circular Merging
I have got 10 marks in 2nd subtask.
I have tried all brute force approach but not getting the AC except the 2nd subtask.
Plz can someone suggest some approach to this.
Is there any concept related to it?
Plz help.I have absolutely no idea.
https://www.codechef.com/JULY19B/problems/CIRMERGE
N integers A1,A2,…,AN are placed in a circle in such a way that for each valid i, Ai and Ai+1 are adjacent, and A1 and AN are also adjacent.
We want to repeat the following operation exactly N−1 times (until only one number remains):
Select two adjacent numbers. Let's denote them by a and b.
Score a+b penalty points.
Erase both a and b from the circle and insert a+b in the space between them.
What is the minimum number of penalty points we can score?
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers a1,a2,…,aN.
Output
For each test case, print a single line containing one integer — the minimum number of penalty points.
Constraints
1≤T≤10
2≤N≤400
1≤ai≤109 for each valid i
Subtasks
Subtask #1 (10 points):
2≤N≤10
ai≤10 for each valid i
Subtask #2 (10 points):
2≤N≤25
a1,a2,…,aN are distinct powers of 2 (including 1)
Subtask #3 (10 points): 2≤N≤100
Subtask #4 (70 points): original constraints
Example Input
1
3
10 10 1
Example Output
32
Explanation
[10,10,1]→[10,11], penalty: 11
[10,11]→[21], penalty: 21
Total penalty: 11+21=32
A small hint will be appreciated.
I have tried all brute force approach but not getting the AC except the 2nd subtask.
Plz can someone suggest some approach to this.
Is there any concept related to it?
Plz help.I have absolutely no idea.
https://www.codechef.com/JULY19B/problems/CIRMERGE
N integers A1,A2,…,AN are placed in a circle in such a way that for each valid i, Ai and Ai+1 are adjacent, and A1 and AN are also adjacent.
We want to repeat the following operation exactly N−1 times (until only one number remains):
Select two adjacent numbers. Let's denote them by a and b.
Score a+b penalty points.
Erase both a and b from the circle and insert a+b in the space between them.
What is the minimum number of penalty points we can score?
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers a1,a2,…,aN.
Output
For each test case, print a single line containing one integer — the minimum number of penalty points.
Constraints
1≤T≤10
2≤N≤400
1≤ai≤109 for each valid i
Subtasks
Subtask #1 (10 points):
2≤N≤10
ai≤10 for each valid i
Subtask #2 (10 points):
2≤N≤25
a1,a2,…,aN are distinct powers of 2 (including 1)
Subtask #3 (10 points): 2≤N≤100
Subtask #4 (70 points): original constraints
Example Input
1
3
10 10 1
Example Output
32
Explanation
[10,10,1]→[10,11], penalty: 11
[10,11]→[21], penalty: 21
Total penalty: 11+21=32
A small hint will be appreciated.
Deja vu: http://www.cplusplus.com/forum/beginner/256890/ and http://www.cplusplus.com/forum/beginner/256955/
| MikeyBoy wrote: |
|---|
| If this is a Codechef problem, you should know that the Codechef adjudicators are aware of this forum, and that people use it to cheat on their contests. If you use this forum to try and cheat, you run the risk of being disqualified. |
| dhayden wrote: |
|---|
| Have you looked at projecteuler.net? They offer interesting programming problems that generally increase in difficulty. Once you solve a problem, you get access to a discussion board that shows how others solved it. Often you'll learn something interesting by looking at how other people solved it. In really extreme cases, someone figures a way to solve it easily with paper and pencil! I'd stay away from codechef. To me, those problems are really contrived, but maybe that's just me. |
Topic archived. No new replies allowed.