e-olymp 94. Problem of prime numbers!

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

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:

  1. 8 2 1
  2. 2 8 1
  3. 2 1 8
  4. 1 8 2
  5. 8 1 2
  6. 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.

Links

ideone
e-olymp

Related Images:

7 thoughts on “e-olymp 94. Problem of prime numbers!

  1. Данная техника называется «перебор с отсечениями». Вы довольно подробно описываете перебор, однако в чем именно заключаются отсечения, умалчиваете. Хотя именно в них и заключается причина того, что Вы не получаете TLE, а не в потенциальном тесте из двух миллиардов чисел.

    Типичная практика для задач америкаских полуфиналов — делать мультитест с «некоторым разумным» числом тестов. Приблизительность во всем — от длин и объемов до налогов, въевшаяся в них еще со школы, дает о себе знать и здесь.

    Кстати, а кто сказал, что «integer number» из условия соответствует C++::int32? Почему не long long или вообще любому целому числу, хоть бы и отрицательному? 🙂

    • Спасибо большое, описал конкретнее. По поводу соответствия целочисленного типа с условием и сказать то нечего ). Как вы и сказали : «с «некоторым разумным» числом тестов», так что можно сказать что повезло что тестов не много, ибо один тест из 15 элементов выполняется примерно за 3,5 с.

    • Спасибо. Однако, пояснения обходят стороной тот факт, что $15!$ получает TLE, а вот $14!$ проходит. Интересная оптимизация, которую стоило бы описать, хоть бы и для Ваших коллег.

    • Спасибо большое, описал.

  2. Здравствуйте Руслан. У вас в коде объявление константы SIZE происходит после её использования для создания массива, пожалуйста исправьте.
    Возможно вместо глобальных констант можно было бы воспользоваться макросами через директиву #define.

    • Для констант есть const, для определения псевдонимов типов есть typedef и в этих случаях использование #define себя не оправдывает.

      Касательно первого Вашего замечания, поддержу.

Добавить комментарий