CODEWITHSUNDEEP
c++algorithmgraphdivision
user1380294
user1380294

Reputation:

graphs divisibility

Given a simple undirected graph containing N vertices numbered 1 to N, each vertex containing a digit from {1,2,..7}. Starting at the vertex 1 with an empty string S, we travel through some vertices (with no limitations) to the vertex N. For every vertex on the way, we add the respective digit to the right of the string S. At last we get S as a decimal integer. You are requested to find such a way satisfying S is divisible by all of its digits, and the sum of digits of S must be as small as possible.

Input

There are several test cases (fifteen at most), each formed as follows:

The first line contains a positive integer N (N ≤ 100).
The second line contains N digits (separated by spaces), the i-th digit is the value of the i-th vertex.
N last lines, each contains N values of {0, 1} (separated by spaces), the j-th value of the i-th line is equal to 1 if there is an edge connecting two vertices (i, j), otherwise 0.

The input is ended with N = 0.

Output

For each test case, output on a line the minimum sum of digits found, or -1 if there's no solution.

example

Input: 4

1 2 1 4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

Output: 7

please guide me

there can be self loops and cycles such that node 1 and node N can be visted any number of times

Upvotes: 4

Views: 482

Answers (3)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

If given graph is transformed to some other graph, where cycles are not allowed, this problem can be solved with Dijkstra's algorithm.

To do this, let's start with string divisibility by 7. Look at this sequence: 1, 10, 100, ... (mod 7). Since 7 is a prime number, 107-1 = 1 (mod 7) because of Fermat's little theorem. Which means 1, 10, 100, ... (mod 7) sequence is periodic and period is 6. This will be used to transform the graph and also this allows to recursively compute Sn (mod 7) using Sn-1 (mod 7): Sn = Sn-1 + 10n%6 * n_th_digit (mod 7).

It's necessary to start shortest path search from node N because this path may be ended at one of the several nodes of the transformed graph. Also this allows to determine quickly (using first 2 nodes of the path), if it is allowed to visit node "5", node"4", and other "even" nodes.

Algorithm's open set (the priority queue) should contain the priority itself (sum of digits) as long as 3 additional bits and 3 remainders: is "4" allowed, is "3" visited, is "7" visited, S % 3, S % 7, and S.length % 6.

Graph should be transformed as follows. Each vertex is expanded to 3 vertexes, one is allowed only for S%3==0, others - for S%3==1 and S%3==2. Then each vertex is expanded to 7 (for S%7), and then each vertex is expanded to 6 (for S.length % 6). It is possible to fit all these expansions to the original graph: just add a 3D array (size 3*7*6) of back-pointers to each node. While searching for the shortest path, the non-empty back-pointers determine algorithm's closed set (they disallow cycles). When shortest path is found, back-pointers allow to reconstruct the sequence of nodes in this path. And the moment when shortest path is found is determined by visiting node 1 with (node_3_not_visited || S%3==0) && (node_7_not_visited || S%7==0).

Upvotes: 2

Yusuf X
Yusuf X

Reputation: 14633

Use the A* search algorithm, where the "cost" is the sum of the digits, and divisibility determines which edges you can traverse.

Upvotes: 0

Imposter
Imposter

Reputation: 2686

First mathematically find the LCM of the numbers given in the set.

lemme paraphrase the scenario .... given a set of numbers... find the LCM then traverse the vetices in such a way that the their path makes the number .Since its LCM it is number whose sum is mininum

For set {0,1,2,3,4} LCM is 12 so travers from 1 to 2 for set {0,1,2,3,4,5,6,7} LCM is 420..(I think i am right)

Upvotes: 0

Related Questions