Petya loves lucky numbers. Everybody knows that positive integers are lucky if their…
- User
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
One night Petya was sleeping. He was dreaming of being the president of some island country. The country is represented by islands connected by two-way roads. Between some islands there is no road way, even through other islands, that's why the country is divided into several regions. More formally, each island belongs to exactly one region, there is a path between any two islands located in the same region; there is no path between any two islands from different regions. A region is lucky if the amount of islands in it is a lucky number.
As a real president, Petya first decided to build a presidential palace. Being a lucky numbers' fan, Petya wants to position his palace in one of the lucky regions. However, it is possible that initially the country has no such regions. In this case Petya can build additional roads between different regions, thus joining them. Find the minimum number of roads needed to build to create a lucky region. Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105). They are the number of islands and the number of roads correspondingly. Next m lines contain road descriptions. Each road is defined by the numbers of islands that it connects: that is, by two integers u and v (1 ≤ u, v ≤ n). Some roads can connect an island with itself; there can be more than one road between a pair of islands. Numbers in each line are separated by exactly one space character.
Output
If there's no solution, output the only number "-1" (without the quotes). Otherwise, output the minimum number of roads r that need to be built to get a lucky region.
Examples
Input
4 3 1 2 2 3 1 3
Output
1
Input
5 4 1 2 3 4 4 5 3 5
Output
-1
Assistant
We need to read and understand the problem. It's about a graph (islands and roads). There are n islands, m roads (undirected, can have self-loops and multiple edges). The graph may be disconnected, so it consists of several connected components (regions). Each region's size (number of nodes) is some number. A region is lucky if its size is a lucky number (composed only of digits 4 and 7). Petya wants to have at least one lucky region. Initially, maybe none. He can build additional roads between different regions (i.e., between islands belonging to different connected components). Building roads can merge regions (by connecting them). The goal: minimum number of roads to build to create at least one lucky region. If impossible, output -1.
Observations: When we add roads, we can connect different components. A road connecting two components merges them into one component (since roads are undirected). We can add multiple roads to connect multiple components. However, note that building roads inside a component is not needed (and not beneficial because we only care about component sizes). Also, building a road between two islands that are already in the same component doesn't change component sizes. So we can only consider adding roads between different components, each such road reduces the number of components by 1 (if connecting two distinct components). Actually, connecting two different components merges them into one component, reducing component count by 1. If we connect more than two components, we may need several roads to fully merge them. To merge k components into one, we need at least k-1 roads (like building a spanning tree). So, the goal is: we have a set of component sizes (list of sizes of connected components in the initial graph). We are allowed to merge any selection of components (by adding roads between them) to form new components. We want to obtain at least one component whose size is a lucky number. We can add roads to merge components, but we must minimize the number of roads added.
Important: We are not required to merge all components; we only need at least one lucky component. The others can remain as they are. So we need to choose a subset of components to merge together (maybe all, maybe some) such that the total size of that subset (sum of sizes) is a lucky number, and we need to minimize the number of roads needed to merge that subset into one component. That cost is (number of components in the subset) - 1, because to connect k components we need k-1 edges (assuming no redundant edges). So we need to find a subset S of component indices (non-empty) such that sum_{i in S} size_i is a lucky number, and minimize (|S| - 1). If initially there is already a component with lucky size, then answer is 0 (since we already have a lucky region). Otherwise, we need to find a combination.
But there is a nuance: The graph can have self-loops and multiple edges. That doesn't affect component sizes or the ability to merge. So we just compute component sizes via DFS or union-find.
Thus problem reduces to: Given a list of positive integers (component sizes) of length compCount (at most n, up to 1e5). Find a non-empty subset S of these numbers such that sum is a lucky number L (L from set of lucky numbers <= n? Actually sum can be up to n because total islands = n, but when merging components, the sum cannot exceed n. So L must be ≤ n. So we consider all lucky numbers up to n (or up to 10^5). Lucky numbers are numbers composed only of digits 4 and 7. There are not many: For n=1e5, the count is limited. Let's generate: 4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777,44444,44447,44474,44477,44744,44747,44774,44777,47444,47447,47474,47477,47744,47747,47774,47777,74444,74447,74474,74477,74744,74747,74774,74777,77444,77447,77474,77477,77744,77747,77774,77777. That's 2+4+8+16+32 = 62? Actually for length 1:2; length2:4; length3:8; length4:16; length5:32; total 62. For n up to 100000, length 6 numbers would be 444444 = 444444 > 100000? Actually 444444 is 444,444 > 100,000, so only up to length 5. So there are at most 62 lucky numbers.
So we need to find a subset of the component sizes that sums to a lucky number L, and minimize (size of subset - 1). This is like a knapsack or subset sum problem with additional objective to minimize number of items used, but we also have the possibility of merging components in any order, but cost is number of components merged -1, independent of which ones. So we need to find a subset with sum = L (lucky) that minimizes the number of elements in subset. Then answer = (min elements - 1). Because merging those elements into one component requires (k-1) roads.
If no such subset exists, answer = -1.
But careful: Could we also merge components by adding roads and not fully merging them into one? Could we create a lucky component by connecting some components and also maybe leaving some connections not fully merged? For a component to be lucky, it must be a connected set of islands. If we add roads that connect multiple components, they become one component only if the graph becomes connected among all those islands. Adding a single road between two components merges them into one. If we add roads that connect more than two components, we need enough edges to make them all connected (i.e., spanning tree). So the minimal number of roads to merge a set of components into one is exactly (|S| - 1). There is no cheaper way. Could we achieve a lucky component without merging all into one? If we have a lucky component, it must be a connected subgraph that includes some islands. If we add roads that connect some components but also keep some parts disconnected, the lucky component would be a subset of islands that are connected. But we could also consider that we might not need to merge all chosen components: we might merge some and leave others not merged, but then the lucky region would be one of the merged ones, but we might have some leftover components that we attached but not fully integrated? Actually, suppose we have components A, B, C. If we add a road between A and B, they become one component of size sizeA+sizeB. If that size is lucky, we have a lucky region and we didn't use C. So we only need to merge exactly those components that we sum, and we don't need to involve any others. So indeed we consider subsets.
But could there be a scenario where merging components via roads also possibly merges with others inadvertently? We can choose roads to connect specific islands. Since we can add roads between any islands we want (presumably we have full control), we can choose to connect exactly the islands from the chosen subset in a tree fashion, and not connect them to any other islands, so we get one component consisting exactly of the union of those islands. So we can isolate that merged component from others. So our model is correct.
Thus the problem is: given multiset of component sizes (counts), find minimum cardinality subset that sums to any lucky number L (≤ n). Output minCardinality -1 if found, else -1.
But we must consider that components themselves may be of size 0? No, each component has at least 1 island, so sizes >= 1.
Now the input size up to 10^5 components (worst case each island isolated, so we have n components of size 1). So we need to solve this efficiently. The number of components could be large (up to 1e5). The subset sum problem with target up to 1e5 is doable with DP, but we need to minimize cardinality. Since n is 1e5, DP over sum up to n with O(n * something) might be okay if we use bounded knapsack? But we have many components of same size, especially many 1's. So we have a multiset of sizes. We need to find the minimum number of components to achieve each possible sum. This is like: given items with weights (sizes) and cost (1 each), we want for each sum the minimum number of items needed to achieve that sum (or infinity if not achievable). Then we check all lucky numbers L, and take min over L of dp[L]. But we have up to 1e5 items and sum up to 1e5. Classic unbounded knapsack? Actually items are limited; each component is a distinct item? But we have many components, each can be used at most once (since each component can be merged only once). So it's a 0/1 knapsack problem with many items (up to 1e5) and capacity n (1e5). That's O(n * number_of_items) = O(1e10) too large.
But we can exploit that component sizes may repeat. We have a frequency distribution of sizes. So we have counts for each size s: freq[s] = number of components of size s. Then we want to know for each total sum, the minimum number of items needed to achieve that sum, using at most freq[s] items of size s. This is a bounded knapsack (multiple items of each size). Capacity = n (1e5). The number of distinct sizes is at most sqrt(2n)? Actually sizes can be up to n, but there could be many distinct sizes. In worst case, if each component size is unique, number of distinct sizes could be up to n (if all components are of different sizes? But total n = sum of sizes, so if each component size is distinct, the number of components is at most about sqrt(2n) if sizes are 1,2,3,...? Actually sum of first k integers is k(k+1)/2 ≈ n, so k ≈ sqrt(2n). So number of distinct sizes cannot exceed about 447 for n=1e5. Because if you have sizes all distinct and each at least 1, the sum of smallest k distinct positive integers is at least k(k+1)/2. So k ≤ O(sqrt(2n)) ≈ 447. So indeed number of distinct sizes is O(sqrt(n)). That's a key observation! But careful: component sizes can be repeated; but distinct sizes are limited because the sum of all sizes is n. If you have many distinct sizes, they must be large? Actually consider: you could have components of sizes: 1, 1, 1,... many 1's, that's not distinct. For distinct sizes, each size appears at least once. The maximum number of distinct sizes is when you have one component of each size from 1 up to some k, and the rest (if any) are sizes ≤ k. But total sum = n, so if you have distinct sizes 1,2,...,k, the sum is at least k(k+1)/2. So k <= sqrt(2n). For n=1e5, sqrt(2*1e5) ≈ sqrt(200000) ≈ 447.2. So indeed distinct sizes ≤ 447. This is important: we have at most around 447 distinct sizes. So we can treat each size as a group with a limited count.
Now we need to solve a bounded knapsack with minimizing number of items. For each size s, we have count c = freq[s]. We want to compute dp[sum] = minimum number of items needed to achieve sum, using items from processed groups, respecting counts. Standard approach: convert bounded knapsack to 0/1 using binary splitting, then run DP. Since total number of items after splitting is O(sum of log(c) per distinct size). With distinct sizes up to 447, and each c could be large (e.g., many size 1 components: c could be up to n). For size 1, c could be 100000. Binary splitting would create about log2(c) items per size, so total items after splitting would be O(number_of_distinct_sizes * log(max_c)). For size 1, log2(100000) ≈ 17, others less. So total items ~44717 ≈ 7600. That's very manageable. Then we can run a 0/1 knapsack DP over capacity n (1e5) with minimization of count. Complexity O(total_items * n) would be 76001e5 = 7.6e8, which might be too high. But we can optimize: Since we care only about minimizing number of items, we can use DP with bitset? Or we can do DP using the classic technique for "minimum number of coins" with bounded quantities, which can be done with DP using deque for each modulo class (monotone queue optimization). But given constraints, maybe 7.6e8 is borderline (C++ with optimizations maybe too slow). We need something more efficient.
Alternative: Since the number of distinct sizes is small, we can use DP by iterating over sizes and for each size, we update dp in a clever way using counts. There is a well-known DP for bounded knapsack with min number of items that runs in O(n * number_of_distinct_sizes) using a technique of DP for each remainder modulo s, and maintaining a deque to compute minimum values within a sliding window limited by count. That would be O(n * distinct_sizes). With n=1e5 and distinct up to 447, that's about 4.47e7, acceptable in C++.
But we need to be careful: The DP is to compute the minimum number of items to achieve each sum. We can initialize dp[0] = 0, others = INF. For each size s with count c, we update dp in a way similar to "multiple knapsack" but for minimization of count. Since we want to minimize number of items, each item has cost 1. So we want to minimize total count. For each s, we consider adding up to c items of that size. The standard technique: for each remainder r in [0, s-1], we process sums j = r, r+s, r+2s, ... up to n. For each such sequence, we maintain a deque to find the minimum dp[j - ks] + k for k from 0..c, but we need to transform the recurrence: dp[j] = min_{0 ≤ k ≤ min(c, j/s)} ( dp[j - ks] + k ). Since dp[j] originally may have some value from previous groups, we consider adding k items of size s. Actually we need to incorporate the current group. The DP can be done by considering the values for each modulus separately, and using a monotone queue to compute the minimum over a sliding window of size c+1.
Specifically, for each remainder r, we iterate t = 0,1,2,... such that j = r + ts <= n. For each t, we consider the value val[t] = dp[r + ts] - t. Then when updating dp_new, we want dp_new[j] = min_{k=0..c, k ≤ t} ( dp_old[r + (t-k)*s] + k ) = min_{k=0..c, k ≤ t} ( dp_old[r + (t-k)*s] - (t-k) ) + t. So we maintain a deque that keeps the minimum of (dp_old[r + (t-k)s] - (t-k)) for k in window. This is typical. So we can compute new dp in O(n) total per distinct size? Actually for each size s, we process O(n) states (all sums) but with the modulus split, total across all remainders is n. So each size takes O(n) time. With distinct sizes up to 447, total O(4471e5) = 44.7 million, which is fine.
Alternatively, we could do DP with binary splitting and then use BFS-like or use bitset? But the monotone queue DP is efficient and easier to code.
But there's nuance: dp values are integers (minimum count). We need to compute dp for sums up to n. dp array size 100001.
Now after DP, we check each lucky number L (<= n). Answer = min(dp[L]) - 1 (since dp[L] is minimum number of components to sum to L). But careful: dp[L] includes the number of components merged. If dp[L] = 0? Only possible if L=0, but L is positive lucky number (≥4). So dp[L] will be at least 1. So answer = dp[L] - 1. But also note that we could possibly create a lucky region by building roads that also involve merging components that we didn't fully include? No, the subset approach is correct.
Now there is a twist: The problem might allow building roads that connect not only components but also within a component? But building within a component doesn't change its size; so it's useless. Also, could we build roads that connect components and also create a lucky region but also increase the size of some other region? No, we only need at least one lucky region; we don't care about others. So we want to minimize number of roads added. So merging a set S yields cost |S|-1.
But is there any possibility of building roads that merge components but also split some region? No, adding roads can only connect components, not split them.
Thus the solution is as described.
Edge Cases: If there is already a lucky component, dp[L] for L = that component size will be 1 (since we can just take that component alone). So answer min - 1 = 0. Good.
If no subset sums to any lucky number, answer -1.
Now we need to be careful: The DP must consider that each component can be used at most once, which we have done.
Now check examples:
Example 1: n=4, m=3 Edges: 1-2,2-3,1-3 → component: islands 1,2,3 connected (size 3), island 4 isolated (size1). So sizes = [3,1]. Lucky numbers up to 4: 4,7,... only 4. We need sum 4. Can we get 4? Yes: merge component size3 and size1 gives sum 4, uses 2 components, cost =1. So answer 1. matches.
Example2: n=5,m=4 Edges:1-2,3-4,4-5,3-5 → components: {1,2} size2; {3,4,5} size3. sizes =[2,3]. Lucky numbers up to 5: 4,7,... 4. Can we sum to 4? 2+? no 2 alone 2, 3 alone 3, 2+3=5 not 4. So no subset sums to 4, and next lucky 7 >5, so impossible => -1. matches.
Thus solution seems correct.
Now we need to implement:
Steps:
- Read n,m.
- Build graph? But we only need component sizes. Use DSU (Union-Find) to process edges. Since m up to 1e5, n up to 1e5, DSU works fine. Need to handle self-loops and multiple edges, but DSU can just union u and v (even if same). Use path compression and union by size.
- After processing all edges, for each node find its root, compute size of each component: we can after unions, count number of nodes per root.
- Get list of component sizes (positive). Count frequency of each size.
Alternatively, we can directly compute sizes via DSU: maintain an array parent, size. After unions, for each root, we have size[root]. Then we get multiset of sizes (excluding zeros). Then count frequencies: map from size to count.
-
Generate all lucky numbers up to n. We can generate by recursion or iteratively. Since n max 100000, we can precompute all lucky numbers <=100000.
-
DP to compute minimum number of components needed to achieve each sum from 0 to n.
Implementation details for bounded knapsack with minimization:
We have dp array of length n+1, initialized to INF (some large number, say n+1 or 1e9). dp[0] = 0.
For each size s (distinct) with count c: We will update dp in-place? But careful: When processing a group, we need to use previous dp values (from groups processed before) to compute new dp. For each s and c, we can do a DP using a temporary array newdp = dp (copy) and then update, but that would double memory. However the monotone queue method typically updates dp in a way that is in-place but ensures we don't use updated values from the same group erroneously. Since the recurrence uses dp_old values (from before processing this group), we need to either work on a copy or process each modulus with a fresh deque and update a new dp array. Simpler: we can use an auxiliary array ndp = dp (copy) and then for each remainder compute using dp as old values and write to ndp. After processing all remainders, set dp = ndp. This is O(n) per size, memory O(n). Acceptable (n=1e5, copying each time might be okay: 447 copies of 1e5 ints ~ 44.7 million integers copy, each 4 bytes ~ 178 MB? Actually 447 * 1e5 = 44.7 million assignments. That's not huge but could be okay in C++ (44.7e6 operations). But we also have DP computations. Still total around 100 million operations, fine.
But we can also do in-place using the deque method with a temporary array per modulus? However copying dp to ndp per size is easy.
Pseudo:
dp.assign(n+1, INF); dp[0] = 0;
for each (s, c) in freq map: ndp = dp; // copy for r in 0..s-1: deque<pair<int,int>> dq; // stores (index, value) maybe. // iterate t = 0,1,... while j = r + ts <= n for t = 0; j = r + ts; j <= n; t++: // val = dp[j] - t (using old dp) int val = dp[j] - t; // maintain deque: remove if out of window (k > c) i.e., indices t - k > c? Actually we need to maintain candidates for k from 0..c. // Standard: For each t, we consider adding candidate with index t (i.e., dp[j] - t). We remove from back while values >= val (since we want min). Then push (t, val). // Then remove from front if t - index > c (i.e., more than c items used). // Then ndp[j] = min(ndp[j], dq.front().value + t) // Actually ndp[j] = min(old dp[j] (not using any of this size) and using some k). But we are building ndp from dp. We should take min of existing ndp[j] (which might have been set from previous groups or previously from this group? Since we are processing each modulus separately, and we are writing to ndp, we need to ensure we are not overwriting incorrectly. Usually we initialize ndp with dp, and then for each j we update ndp[j] with the possibility using items from this group. So we compute candidate = dq.front().val + t; if candidate < ndp[j], set ndp[j] = candidate. // after loop, dp = ndp.
But careful: The dp[j] in val = dp[j] - t uses the old dp (before considering this group). That's correct because we are considering adding items from this group to the previous groups. The deque stores old dp values minus index.
Implementation details:
For each remainder r (0 <= r < s): deque indices; or deque<pair<int,int>> (index t, value) for t = 0; (j = r + t*s) <= n; t++: // current candidate from old dp at this position: cur = dp[j] - t cur = dp[j] - t; // while deque not empty and its back value >= cur, pop back while (!dq.empty() && dq.back().second >= cur) dq.pop_back(); dq.push_back({t, cur}); // remove if front index is < t - c (i.e., window size > c) while (!dq.empty() && dq.front().first < t - c) dq.pop_front(); // now best value = dq.front().second + t if (dq.front().second + t < ndp[j]) ndp[j] = dq.front().second + t; After all remainders, dp = ndp.
But we must also consider the possibility of using 0 items from this group, which is already covered because ndp initially = dp, and the candidate from deque includes the possibility of using 0 items? Actually if we use 0 items, that corresponds to k=0, which is represented by considering the candidate when t =? The deque includes the candidate for k=0 when the window includes the current t? Let's verify: For a given j, we are considering all k from 0 to c such that k <= t (where t = (j - r)/s). The recurrence is dp_new[j] = min_{k=0..min(c,t)} (dp_old[j - ks] + k). The transformation: let t' = t - k, then dp_old[j - ks] + k = (dp_old[r + t'*s] - t') + t. So we need to take min over t' from max(0, t-c) to t of (dp_old[r + t'*s] - t') + t. The deque maintains min over t' in sliding window of size c+1 of (dp_old[r + t'*s] - t'). At step t, we have candidates t' from t-c to t. So the min is taken correctly. The case k=0 corresponds to t' = t (i.e., using 0 items of this size), and it's included because t' = t is in the window (since t - t' = 0 <= c). So yes, the deque includes the current cur (which corresponds to t'=t) after pushing it. However, the candidate from using 0 items is dp_old[j] (since k=0). That would be cur + t = (dp_old[j] - t) + t = dp_old[j]. So the deque method naturally includes the possibility of not using any from this group. But careful: We push cur before computing the min? Usually order: we compute candidate after pushing current and then cleaning the window. For t=0, push cur (dp[r] - 0). Then window contains t'=0. front is that. candidate = cur + t = dp[r] - 0 + 0 = dp[r]. So ndp[r] gets min of its existing value (which is dp[r]) and candidate (dp[r]), no change. That's fine.
Thus algorithm works.
But note: dp values can be INF, so need to handle large numbers. INF can be something like n+1 (since max needed items is at most n). Use n+5 as INF.
Also, after processing all groups, dp[sum] holds min number of components to achieve that sum (or INF if impossible).
Now we iterate over lucky numbers L from list (L <= n). Find minCount = min(dp[L]). If minCount remains INF, answer = -1; else answer = minCount - 1.
Now check: What if we have dp[L] = INF? Then no subset.
Edge Cases: Could there be scenario where merging more components than needed to achieve lucky number gives a lower cost? Wait cost = |S|-1, so minimizing |S| is equivalent to minimizing cost, since cost = cardinality - 1. So min cost corresponds to min cardinality. However, is there any scenario where we could achieve a lucky region without merging a set S into one component but by building roads that partially merge some components and also keep others? For example, suppose we have components of sizes 2 and 2, and we want a lucky region of size 4. Merging both gives cost 1 (2-1=1). But could we achieve a region of size 4 by connecting one component to part of another? Not possible because components are whole; you can't split a component without removing roads (can't delete roads). So you must merge entire components.
Thus the subset approach is correct.
Now confirm with more complex scenario: Suppose we have components of sizes 1,1,1,1 (four components). Lucky number 4: we can merge all four: cost 3. But maybe we could merge three (1+1+1=3) not lucky. So minimal cost for sum 4 is 3. But could we achieve a lucky region of size 4 by merging two components (1+1=2) and then adding a road inside a component? No, that wouldn't change size. So indeed need four ones.
Now complexity: Distinct sizes up to about sqrt(2n). But we also have to consider that component sizes can be large, but number distinct small. The monotone queue DP per size s runs O(n). That's okay. But we also need to sort or iterate through freq map. We'll just loop over entries.
Implementation notes:
-
Use union-find to compute component sizes.
-
After DSU, we can count sizes: vector compSizes; for i from 1 to n, if parent[i]==i, sizes.push_back(size[i]); (but careful: we need to handle path compression, but we can just loop and find root for each i, but more efficient to iterate over roots directly). I'll use DSU with parent array and size array. After unions, for i from 1 to n, if parent[i]==i, then push size[i] into list. Then compress frequencies: use unordered_map or map from size to count. Since distinct sizes small, map is fine.
-
Generate lucky numbers: recursion or loop. Write a function that generates all numbers composed of digits 4 and 7 up to n. Use queue or recursion: start with 0, then for each number, append 4 and 7 if ≤ n.
-
DP: n up to 100000. dp array of ints size n+1. Use vector dp(n+1, INF). INF = n+5.
-
For each (size, cnt) in freq map:
- vector ndp = dp; // copy
- for r in 0..size-1: deque<pair<int,int>> dq; // (index t, value) int t = 0; for (int j = r; j <= n; j += size, t++) { int cur = dp[j] - t; // maintain deque while (!dq.empty() && dq.back().second >= cur) dq.pop_back(); dq.push_back({t, cur}); // remove out of window while (!dq.empty() && dq.front().first < t - cnt) dq.pop_front(); int best = dq.front().second + t; if (best < ndp[j]) ndp[j] = best; }
- dp = move(ndp);
But we must be careful: dp values might be INF, and INF - t could overflow or become large negative? Actually INF is big, but subtracting t may still be big. But it's okay because we use comparisons, and we don't want INF values to affect min. Since INF is large, cur will be large, but when we compare with other cur in deque, if all are INF, then best will be INF + t? Actually best = dq.front().second + t = (INF - t_front) + t. If dq.front().second is INF, then best becomes INF - t_front + t. That could be less than INF if t > t_front? That could be problematic because INF is not a true infinite but just a sentinel. If dp[j] = INF for many j, then cur = INF - t, which might be less than INF? Actually if INF is set to a very large number (like 1e9), then INF - t is still large, but when we add t back, we get INF again? Let's compute: best = (INF - t_front) + t. If t_front and t are indices, this could be INF + (t - t_front). Since t - t_front could be positive, best could exceed INF, but that's not correct because dp[j] should be INF if not reachable. Using sentinel INF, we need to ensure that if all candidates are INF, the result remains INF. However, because of the arithmetic, best might become INF + (t - t_front) which is larger than INF, but we take min with ndp[j] which is INF initially. So we might erroneously set ndp[j] to INF + something, which is larger than INF, but then later min with INF may keep INF? Actually if best = INF + delta > INF, and ndp[j] = INF initially, then min(INF, INF+delta) = INF, so no problem. But if we later compare with other candidates, we might incorrectly think that a candidate with value INF - t_front is less than another INF - t? But both are huge. The main issue is that we should not allow INF values to be considered as valid candidates that could produce a finite best when combined with others. But they won't produce a finite best because INF is huge. However, there is a risk of overflow if INF is too large (e.g., INT_MAX). But we can set INF to something like 1e9, and n is 1e5, so INF - t is still positive and large. The deque comparisons will treat INF - t as large numbers, but they are all large, but the min will still be INF - t_front if all are INF? Actually if all dp[j] are INF, then cur = INF - t. Since INF - t is still very large but decreasing as t increases? That would cause the deque to keep only the smallest cur, which would be the one with largest t (since INF - t gets smaller as t increases). That would be problematic because those INF values are not actually reachable, but they are treated as numbers. Then when we compute best = (INF - t_min) + t, that might be less than INF? For example, suppose INF = 1e9, at t=0, cur = 1e9; t=1, cur = 1e9 - 1; t=2, cur = 1e9 - 2; So the deque will keep the smallest, say at t=2 cur = 1e9 - 2. Then for t=2, best = (1e9 - 2) + 2 = 1e9, which is INF. So still INF. For t=3, best = (1e9 - 2) + 3 = 1e9 +1, > INF, but min with INF remains INF. So no problem. However, if we have a mix of finite and INF, the deque will work correctly because finite values will be smaller than INF and will be preferred. So it's okay as long as we ensure INF is large enough that INF + something doesn't overflow. Use INF = 1e9.
But we need to be careful when computing cur = dp[j] - t; if dp[j] is INF, cur might become negative if INF is not large enough relative to t? t can be up to n/size, which at worst when size=1, t up to n=100k. So INF - t should remain positive and still large. Set INF = 1e9 is safe (1e9 - 100k = 999900000 still positive). So fine.
Alternatively, we could treat INF as a special value and skip if dp[j] == INF. But the deque method with subtraction may still work with INF sentinel as described. Usually in competitive programming we just use a high number.
Edge case: For size s=0? Not possible since component size >=1.
Now after DP, we compute answer.
But wait: is there any alternative approach? Another possibility: Because we only need the minimum cardinality for sums that are lucky numbers, perhaps we could use BFS-like DP with bitset? But the described DP is fine.
Now complexity: Distinct sizes ≤ about 447. For each size, we iterate over all n+1 sums, but with modulus loops it's n operations per size. So total O(distinct * n) ≤ 447*100000 = 44.7 million, each operation includes deque operations (amortized O(1)). So overall fine.
But we need to be careful about copying dp to ndp for each size: that adds another O(n) per size, making total about 89 million assignments, still fine.
But we might reduce copying by using two arrays and swapping: we can allocate dp and ndp, and after processing a size, we swap them. For each size, we initialize ndp = dp (copy). That copy is O(n). So total O(distinct * n) ~45 million copy operations, which is acceptable.
Memory: two arrays of size 100001 ints, about 800KB each.
Now we should consider whether the DP approach yields the correct min number of components. But wait: The DP we described computes the minimum number of items (components) needed to achieve a sum, but it treats each component as an item with weight size and cost 1. This is correct. However, there is nuance: When merging components, the number of roads needed is (|S| - 1). But is it always possible to merge exactly the chosen components without affecting others? Yes, by building roads only between islands from these components, we can connect them into one component. But could there be a restriction that roads must be built between different regions? The problem says "Petya can build additional roads between different regions". So he can only build roads between islands that are in different regions initially? Or after building some roads, the regions change; but he can continue building roads between currently different regions. However, the problem statement: "In this case Petya can build additional roads between different regions, thus joining them." This implies that at the time of building a road, the two islands must be in different regions. But as we build roads, regions merge. So the process of merging a set S of initial components can be done in any order: start with components in S, we can connect any two of them with a road as long as they are currently in different regions. Initially, all components are separate. So we can connect them one by one; each road connects two distinct regions (which are initially separate or after merges). So after k-1 roads, they become one region. So yes, merging set S is feasible with exactly |S|-1 roads.
But we must also consider that when we add roads, we might inadvertently merge other components that we didn't intend to merge? Not if we only connect islands from the chosen set S. However, what if the graph is such that some islands from other components are in between? No, because roads are only built between two islands we choose; we can choose which islands to connect. So we can avoid connecting to other components. So it's fine.
Thus the DP approach is valid.
Now we need to ensure we consider subsets of components that sum to exactly a lucky number L. Could there be a case where we need to build roads that also connect some components outside S but then break them? No, can't break. So we must sum exactly.
Now check some tricky cases: Suppose we have components of sizes 2,2,2, total n=6. Lucky numbers up to 6: 4,7? 7>6, so only 4. To get sum 4, we can take two components of size2: cost=1. So answer 1. DP should give min cardinality 2.
Suppose components sizes: 3,3. Lucky numbers: 4? Not. 7? 3+3=6, not 7. So no subset, answer -1. But maybe we could merge both (cost 1) to get size6, not lucky, then maybe add a road to somewhere else? But that would increase the size? Adding roads only merges components, cannot increase size beyond total n. If we merge all components, size becomes 6, still not lucky. So impossible.
Suppose components sizes: 1,1,1,1,1 (5 ones). Lucky number 4: take 4 ones cost 3. Lucky number 7 not reachable (max 5). So answer 3.
Now think about DP when component sizes are large relative to n. That's fine.
Now we also need to handle the case where there might be a lucky component already: dp[L] = 1 for that size L, answer 0.
Now we must consider if we have to output -1 when no subset sum equals a lucky number. But is it ever impossible? The maximum possible sum we can achieve is n (by merging all components). So if there is a lucky number L ≤ n that can be formed as sum of some subset of component sizes, then we can achieve it. However, it's possible that no lucky number ≤ n can be expressed as sum of any subset. That includes the case where n < smallest lucky number 4? But n≥1. If n <4, then no lucky number exists at all (since smallest lucky is 4). Then answer is -1? Let's see: If n<4, there is no lucky number ≤ n, so we cannot ever have a lucky region because any region's size must be between 1 and n, and lucky numbers start at 4. So impossible => -1. That is covered because we only consider lucky numbers ≤ n, and if none exist, answer -1. But also, if there are lucky numbers but none can be formed as subset sum, answer -1.
Edge case: n=1,2,3: no lucky numbers, answer -1.
Now double-check constraints: n,m up to 1e5, edges may have self-loops, multiple edges. DSU will handle.
Now about DP: There is a nuance: The component sizes we have are the sizes of connected components. However, when we merge components, we effectively take a set of components and merge them into one. But what if we want to use a component multiple times? No, each component can be used at most once because it's a distinct set of islands. So DP is 0/1.
Now we must ensure that the DP accounts for the fact that we can choose any subset of components, not necessarily all. That's fine.
Now complexity wise, for each distinct size, we run the modulus loop. However, there is a catch: The DP algorithm described works for bounded knapsack when we want to minimize the number of items. But we need to confirm that the DP correctly handles the "min number of items" for each sum. The algorithm essentially computes for each sum the minimum total count using items from processed groups. Since each group can be used up to c times, the sliding window method is standard for "min cost" where each item has cost 1. So it's correct.
But there is another nuance: The DP we described treats each item weight s with cost 1. However, we are not trying to minimize cost but number of items. That is exactly cost =1 per item. So it's a classic bounded knapsack with cost per item = 1. The sliding window DP works for minimizing total cost (or maximizing value) with bounded quantities, as long as the cost function is linear in the number of items used (i.e., each item adds the same cost). That's the case.
Now we can implement.
But we could also use an alternative: Since we only care about the minimum cardinality for sums that are lucky numbers, we could try BFS on sums using the idea of coin change with limited coins to compute minimal number of coins to reach each sum. This is exactly DP. So sliding window is good.
Now potential pitfall: The DP array size is n+1; but we need to consider sums up to n. n can be 1e5. Good.
Now implementation steps in detail:
- Read n, m.
- Initialize DSU: parent[n+1], sz[n+1] = 1 for each.
- For each edge: read u,v; union(u,v). (If u==v, union handles it, but DSU union should handle self-loop by checking same root, but that's fine).
- After all unions, for i=1..n: find root (or just iterate over parents where parent[i]==i). But careful: after path compression, some parents may not be roots? We can loop and do find(i) to compress fully, but it's easier: vector compSizes; for i=1..n: if parent[i] == i (i.e., root) then push sz[i]. However, DSU with union by size, the root's sz is the size of component. But after unions, there may be nodes with parent not equal to root? Actually we maintain that for each root, parent[root] = root, and sz[root] is component size. For non-root nodes, parent is not itself. So we can just iterate over i from 1 to n and if parent[i]==i, add sz[i]. This yields the list of component sizes.
But what about path compression? We might have performed path compression during unions, but not guaranteed all nodes are compressed. However, root nodes are still roots. So that works.
Alternatively, we can use find(i) for each i to get root and then count frequencies using a map. That may be simpler and ensures we get correct sizes even if we haven't compressed all. We'll do:
unordered_map<int,int> rootCount; or just array count[n+1] = 0; for i=1..n: root = find(i); count[root]++. Then after loop, sizes are values of count where >0.
We'll use DSU with path compression and union by size.
-
Build frequency map of sizes: unordered_map<int,int> freq; for each component size (value of count[root]), freq[sz]++.
-
Generate lucky numbers up to n: use recursion: generate_lucky(x): if x>n return; if x>=4 lucky_list.push_back(x); generate_lucky(x10+4); generate_lucky(x10+7); start with 0? Actually start with 4 and 7: call generate(4) and generate(7). Ensure numbers >=4? Lucky numbers are positive integers whose decimal representation contains only digits 4 and 7. So 4,7,44,47,... So we generate from 4 and 7. We'll store in vector lucky.
-
DP as described.
Now implement DP:
const int INF = 1e9; // or n+5? Use n+5 because max needed count cannot exceed n (if we take all components). So INF = n+5 is fine. vector dp(n+1, INF); dp[0] = 0;
for (auto& p : freq) { int s = p.first; int c = p.second; vector ndp = dp; // copy // Process for each remainder r for (int r = 0; r < s; r++) { deque<pair<int, int>> dq; // each element: (index t, value) int t = 0; for (int j = r; j <= n; j += s, t++) { // cur = old dp[j] - t int cur = dp[j] - t; // maintain deque while (!dq.empty() && dq.back().second >= cur) { dq.pop_back(); } dq.push_back({t, cur}); // remove out of window: indices < t - c while (!dq.empty() && dq.front().first < t - c) { dq.pop_front(); } // best = dq.front().second + t int best = dq.front().second + t; if (best < ndp[j]) { ndp[j] = best; } } } dp = move(ndp); }
But note: dp[j] might be INF, and cur = INF - t could be large negative if INF is not large enough? Actually INF - t might be still large, but if INF is n+5, then for t up to n, INF - t could become as low as 5, which is not INF and could be mistaken as reachable. For example, if INF = n+5 = 100005, and t=100000, then cur = 100005 - 100000 = 5, which is a small number. That would be interpreted as a valid candidate, but dp[j] was INF originally meaning unreachable. This would cause errors. So we must ensure INF is large enough that even after subtracting t up to n, it still remains larger than any possible real value. The maximum possible real dp value is at most number of components, which is at most n (if each component size 1, then max sum n uses n components). So real dp values ≤ n. So we can set INF to something like n+1 or n+5? But then INF - t could be as low as 5 when t close to n. That's less than n, so it would be considered as a candidate, leading to false reachable sums. That's bad.
We need to avoid that: We should only consider dp[j] that are not INF when computing cur. So we should treat INF as unreachable. In the DP transition, we should only consider dp[j] that are finite. So we need to adjust the algorithm to handle INF properly. One approach: Use a large INF, e.g., 1e9, so that INF - t stays large (around 1e9 - 1e5) which is still >> n, and will not be selected as min because real values are ≤ n. But careful: In deque, we compare values; if we have some finite values, they will be much smaller than INF. If all values are INF, then the deque will hold INF - t values. But when we compute best = (INF - t_front) + t, we get INF + (t - t_front). If t_front <= t, this could be INF or larger. However, it could be that t_front is less than t, then best = INF - t_front + t = INF + (t - t_front). That may be > INF, but still huge. When we compare to ndp[j] which might be INF (1e9), best may be > INF, but we take min. So best > INF, so ndp[j] stays INF. So no problem. However, if we set INF = n+5, then INF - t_front could be as low as small numbers, and best may become small erroneously. So we need INF to be sufficiently larger than any possible real value plus n. Since real dp values ≤ n (max components used), we can set INF = 1e9 (or 1e7) safe. I'll set INF = 1e9.
But then we need to ensure that INF - t does not underflow if t > INF? t max 1e5, INF 1e9, safe.
Thus we'll set INF = 1e9.
But we also need to be careful when we compute cur = dp[j] - t; if dp[j] is INF (1e9), cur is around 1e9 - t, which is still huge, but it's not negative. So it's okay.
Now after DP, we compute answer.
But wait: Could there be a case where we need to use more than n components? No, because total number of components is ≤ n. So max dp value ≤ n. So INF = n+5 is not safe because of subtraction. So use INF = 1e9.
Now we check DP for correctness with example: sizes: {3,1}. freq: 3:1, 1:1.
Initialize dp[0]=0, others INF.
Process size 3, count 1. ndp = dp. For r=0: process j=0,3,... up to 4? n=4. t=0, j=0: cur = dp[0]-0=0. dq: push (0,0). front (0,0). best=0+0=0, ndp[0]=min(0,0)=0. t=1, j=3: cur = INF-1? Actually dp[3] is INF, cur = INF-1. dq push (1, INF-1). Since cur is huge, while back.second >= cur? back.second=0, 0 >= INF-1? false. So dq now (0,0),(1,INF-1). front index 0, check if < t-c? t=1, c=1, t-c=0, front index 0 is not <0, so keep. best = front.second + t = 0+1=1, ndp[3]=min(INF,1)=1. t=2, j=6 >4? not processed. Also r=1,2 similar but j start at 1,2 etc. After processing size 3, dp becomes: dp[0]=0, dp[3]=1, others INF.
Now process size 1, count 1. ndp = dp. For r=0: iterate j=0,1,2,3,4. t=0,j=0: cur=dp[0]-0=0; dq push (0,0); best=0; ndp[0]=0. t=1,j=1: cur=dp[1]-1=INF-1; push; dq: (0,0),(1,INF-1). front index 0, check window: t-c=0, so keep. best=0+1=1; ndp[1]=min(INF,1)=1. t=2,j=2: cur=dp[2]-2=INF-2; push; dq: (0,0),(1,INF-1),(2,INF-2). front index 0 still? window: t-c=1, since