The task is taken from e-olymp
Task
One of the most difficulties of an instructor is question design for the final-term exam. Dr. Ghavamnia teaches “Fundamentals of Algorithms” at University of Isfahan (UI) and has designed a good practical algorithmic problem for his exam. He wants that students use all of their algorithmic skills to code this problem as best and efficient as they can. The problem is as follows: a ring is composed of [latex]N[/latex] circles numbered from [latex]1[/latex] to [latex]N[/latex] as shown in diagram. You are given [latex]N[/latex] integer numbers. Put these numbers into each circle separately with the condition that sum of numbers in three adjacent circles must be a prime.
Each test case may have several solutions and your task is to find the one with minimum weighted sum. Weighted sum is defined as the sum of products of each number in circle by the sequence number of that circle. For instance, the weighted sum in above diagram is [latex]36[/latex] (and also it is the minimum).
Input
The first line of input contains a single integer, the number of test cases. Following, there is one line for each test case. Each test case begins with one integer, [latex]N[/latex] ([latex]3 \leq N \leq 15[/latex]), which is the number of circles. Next [latex]N[/latex] integers are the given numbers to put in circles (all between [latex]1[/latex] and [latex]100[/latex], inclusively).
Output
There should be one line for each test case in output. If there’s no way for building the ring, the word «impossible» should be outputted, or otherwise, a single integer which is the minimum weighted sum.
Tests
|
№
|
Inputs | Outputs |
|
1
|
5 4 1 3 7 9 4 1 1 3 5 15 11 6 2 3 2 14 1 2 10 7 2 2 3 6 2 9 1 1 1 2 2 2 2 2 2 7 1 2 3 4 5 6 7 |
36 imposible 396 72 imposible |
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <vector> #include <string> using namespace std; int length; vector <int> input(16); vector <int> output(16); bool used[16]; const int SIZE = 350; bool isPrime[SIZE]; const int INF = 2147483647; long min; bool prime(int k) { return isPrime[k]; } void init() { // initialization for Sieve of Eratosthenes for (int i = 0; i < SIZE; i++) { isPrime[i] = true; } for (int i = 2; i * i < SIZE; i++) { if (isPrime[i]) { for (int j = i * i; j < SIZE; j += i) { isPrime[j] = false; } } } } void perm(int pos) { if (pos == length) { if (!prime(output[pos - 1] + output[0] + output[1]) || !prime(output[pos - 1] + output[pos - 2] + output[0])) { return; } for (int z = 0; z < length; z++) { long temp = 0; for (int i = 1; i <= length; i++) { temp += i * output[i - 1]; } if (temp < ::min) { ::min = temp; } int k = output[0]; for (int j = 0; j < length - 1; j++) { output[j] = output[j + 1]; } output[length - 1] = k; } return; } for (int i = 0; i < length; i++) if (!used[i]) { output[pos] = input[i]; if (pos >= 2 && !prime(output[pos] + output[pos - 1] + output[pos - 2])) { continue; } used[i] = true; perm(pos + 1); used[i] = false; } } int main() { string f; init(); int t; cin >> t; for (int j = 0; j < t; j++) {::min = INF; scanf("%d", &length); for (int i = 0; i < length; i++) { scanf("%d", &(input[i])); } output[0] = input[0]; used[0] = true; perm(1); f = (::min == INF ? "impossible" : to_string(::min)); printf("%s\n", f.c_str()); } return 0; } |
Solution
We need all permutations of our array and if permutation suits us update [latex]min[/latex] value. To check if number is prime I use Sieve of Eratosthenes. To get all permutation I use recursive function which works in this way: 
We accumulate an array in all possible ways. What we do:
- Fixed empty position in array with a value
- Remember that we used this value
- Find all permutations of array with size which is smaller by 1
- Forget that we used this value (to use it in next permutations)
We stop when we accumulate an array with size we need and check if this permutation suits us(if sum of all triples of this circle are prime). If yes update answer(if it is less than answer). So if we send this solution to server we will get time limit. We need to reduce permutations which do not suit us. To speed up our program we can reduce amount of permutations in this way: if we find out that sum of previous three numbers, which are fixed, is not prime, we do not need to continue this branch of recursion. Really if in our array we found that one sum of three number is not prime we do not need to accumulate this array further. But anyway we get time limit.
Let’s see the differences in complete array where any some of three numbers is prime number.
Input: 8 2 1
Let’s find all suitable permutations:
- 8 2 1
- 2 8 1
- 2 1 8
- 1 8 2
- 8 1 2
- 1 2 8
As you can see first three are different with shifts. Last three are also different with shifts. So we can fix one element find all permutations we need with less by 1 amount of elements and then shift all elements of every array to get all possible permutations which are correct as you can see above (1,2,3) (4,5,6). In the worst case it will work not for [latex]15![/latex] but for [latex]14![/latex]. And now we get Accept.
The complexity is [latex]O(n!)[/latex]
Why I did not get time limit at all (because of complexity)? In task said than amount of test which works with [latex]O(n!)[/latex] can be huge. But who will make so many tests? In our case there are near 5 tests in one.
Для отправки комментария необходимо войти на сайт.