View

```go package main import ( "bufio" "fmt" "os" ) func main() { reader := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(reader, &n, &k) var s, t string fmt.Fscan(reader, &s) fmt.Fscan(reader, &t) // We need to choose k strings from [s, t] (all of length n, consisting of 'a' and 'b') // to maximize the number of distinct prefixes (of length 1..n) of the chosen strings. // First, count total number of strings in [s, t] // Each string of length n over {a,b} can be seen as a binary number (a=0, b=1) // Key insight: We want to maximize the number of distinct prefixes. // Think of the binary trie of depth n. Each string corresponds to a leaf. // A prefix of length i corresponds to an internal node at depth i. // The number of distinct prefixes = number of trie nodes (excluding root) that have at least one selected leaf descendant. // Strategy: We want to greedily pick strings that add the most new prefixes. // The first string adds n prefixes. Each subsequent string shares some prefix with existing strings. // To maximize, we want strings that diverge as early as possible. // Let's think about it differently. Consider the trie. The number of distinct prefixes // equals the number of edges in the minimal subtree spanning all selected leaves. // We want to maximize this. // For a set of leaves, #prefixes = sum over all internal nodes of (1 if at least one descendant leaf is selected). // Equivalently, for each depth d from 1 to n, count the number of distinct prefixes of length d among selected strings. // Let's compute for each prefix (node in trie), how many leaves in [s,t] are descendants. // Then greedily: we process by BFS/level order. We want to "activate" as many nodes as possible. // A node is activated if at least one of its descendant leaves is selected. // Actually, let's think about it as: we have a budget of k strings. // For each node at depth d (prefix of length d), let cnt(node) = number of strings in [s,t] // that have this prefix. A node contributes 1 to the answer if we select at least 1 of its descendants. // We process the trie top-down. At each node, we decide how many of our k strings go left vs right. // We want to maximize the number of nodes with >0 strings passing through them. // Let me think of it as: for a node with available count c (strings in [s,t] with this prefix), // and we assign m strings to this node (m <= c, m <= remaining budget), // this node contributes 1 + best(left child, ...) + best(right child, ...). // We can solve this with a recursive approach on the trie, but n can be 5*10^5 so we need O(n) or O(n log n). // Let's count for each prefix of length d (0..n), how many strings in [s,t] start with that prefix. // There are up to 2^d such prefixes, which is too many. // But many of these counts are either 0 or "full" (2^(n-d)). The "interesting" prefixes are those // that are prefixes of s or t. There are O(n) such prefixes. // Let me think about the structure. Let p = longest common prefix of s and t (length lcp). // For depths <= lcp, there's exactly one prefix with nonzero count. // At depth lcp+1, s goes one way and t goes the other (s goes 'a' side, t goes 'b' side since s < t after lcp). // Actually s[lcp] < t[lcp] means s[lcp]='a' and t[lcp]='b'. // After lcp, we have two "boundary paths": one following s and one following t. // Along the s-path, at each step if s goes left ('a'), the right subtree is fully available. // Along the t-path, at each step if t goes right ('b'), the left subtree is fully available. // So the trie decomposes into: // 1. The common prefix path (length lcp) // 2. The s-boundary path from depth lcp+1 to n // 3. The t-boundary path from depth lcp+1 to n // 4. "Full" subtrees hanging off the boundary paths // 5. Possibly full subtrees between s-side and t-side at depth lcp+1 (but since alphabet is {a,b}, at depth lcp+1 s goes to 'a' child and t goes to 'b' child, no room between them) // Let me implement this carefully. // Compute lcp lcp := 0 for lcp < n && s[lcp] == t[lcp] { lcp++ } if s == t { // Only one possible string, k >= 1 so we pick it, answer = n fmt.Println(n) return } // s[lcp] = 'a', t[lcp] = 'b' // Now let's collect all "available subtrees" with their sizes (number of available leaves) // and the number of new prefix nodes they'd contribute. // Structure: // Common prefix: depths 1..lcp, each has exactly 1 node -> contributes 1 each if we pick anything (which we will since k>=1) // At depth lcp+1: two children. Left child is on s-path, right child is on t-path. // Both contribute 1 node each. // s-boundary path from depth lcp+1 to depth n: // At each depth d from lcp+1 to n-1, the s-path node has two children. // One child is on the s-path (continues to depth d+1), the other is a "free" subtree. // If s[d] = 'a', s continues left, and the right subtree is fully available with 2^(n-d-1) leaves. // If s[d] = 'b', s continues right, and the left subtree has 0 available leaves (all those strings < s... wait no). // Hmm, I need to be more careful. The s-boundary: strings >= s that share prefix with s. // At the node corresponding to s[0..d-1], if s[d]='a': // - left child (a): continue along s-path (further restricted) // - right child (b): all 2^(n-d-1) leaves are >= s (since they're to the right), fully available // If s[d]='b': // - left child (a): 0 available (all strings with this prefix are < s) // - right child (b): continue along s-path // Similarly for t-boundary: strings <= t that share prefix with t. // At the node corresponding to t[0..d-1], if t[d]='b': // - right child (b): continue along t-path // - left child (a): all 2^(n-d-1) leaves are <= t, fully available // If t[d]='a': // - right child (b): 0 available // - left child (a): continue along t-path // At depth n (leaf level), the s-path leaf (string s itself) has count 1, // and the t-path leaf (string t) has count 1. // So we collect "full subtrees" along the way. Each full subtree rooted at depth d has: // - 2^(n-d) leaves // - if we pick m leaves from it (1 <= m <= 2^(n-d)), it contributes some number of prefix nodes. // Specifically, a full binary subtree of depth (n-d) with m leaves selected: // the number of nodes (prefixes) activated = ? We want to maximize this. // In a full binary tree of depth h (2^h leaves), picking m leaves optimally: // f(h, m) = h*m if m <= ... actually let me think. // f(0, m) = 0 if m=0, but m can be 0 or 1 at a leaf (leaf = string, depth=0 subtree has 1 leaf) // Wait, a subtree rooted at depth d has height (n - d). It has 2^(n-d) leaves. // The root of this subtree is at depth d, so it's a prefix of length d. // The prefixes contributed by this subtree are at depths d+1, d+2, ..., n. (The root itself is counted by the parent.) // Wait, actually the root of the subtree IS a prefix of length d. If it's a "free" subtree hanging off the boundary, // the root node itself needs to be counted too. // Let me redefine. Let's say we have pieces: // 1. The main path has lcp nodes (depths 1..lcp) always activated. // 2. At depth lcp+1, we branch into s-side and t-side (2 more nodes). // 3. Along s-side from depth lcp+1 to n, there are (n - lcp) nodes on the path. // Similarly for t-side. // But the node at depth lcp+1 is already counted in point 2. // So s-path has nodes at depths lcp+1, lcp+2, ..., n. That's n-lcp nodes. // Similarly t-path has n-lcp nodes. // The node at depth lcp+1 is different for s and t side, so no overlap. // Total path nodes: lcp + (n - lcp) + (n - lcp) = 2n - lcp. // But we need k >= 2 to activate both branches. If k = 1, we can only go down one path. // Let me approach this differently with a cleaner model. // We'll enumerate all the "subtree pieces" that we can allocate strings to. // Each piece is either: // (a) A full subtree (all leaves available) of some height h, where picking m (1..2^h) leaves // gives f(h, m) = "number of internal nodes activated" including the root of the subtree. // (b) A single leaf on the boundary path. // For a full binary tree of height h (so 2^h leaves, 2^(h+1)-1 total nodes... wait let me be precise). // A subtree rooted at depth d, with leaves at depth n: height = n - d. // Number of leaves = 2^(n-d). // If we pick m leaves, the max number of NODES (at depths d, d+1, ..., n) activated: // This includes the root of the subtree at depth d. // f(h, m) where h = n - d: // f(0, 0) = 0, f(0, 1) = 1 (the leaf itself, which is at depth n, a prefix of length n) // For h > 0: f(h, m) = 1 + max over splits (m1 + m2 = m, 0 <= m1 <= 2^(h-1), 0 <= m2 <= 2^(h-1)) of // (f(h-1, m1) + f(h-1, m2)) // where if m1=0, f(h-1,0) = 0 (that child not activated); similarly for m2. // In a full subtree of height h, with m leaves selected optimally: // The max #nodes = ? // Strategy: distribute as evenly as possible to activate as many nodes as possible. // If m = 0: 0 // If m >= 1: we activate the root (1 node), then distribute to children. // If m = 1: we go down one path, activating h+1 nodes total (root + h levels below). // Actually root to leaf is h edges, h+1 nodes. So f(h, 1) = h + 1. // If m = 2: go down both children each with 1. f(h, 2) = 1 + 2*f(h-1, 1) = 1 + 2*h. // (for h >= 1) // If m = 3: 1 + f(h-1, 1) + f(h-1, 2) = 1 + h + (1 + 2(h-1)) = 1 + h + 2h - 1 = 3h. // (for h >= 2) // If m = 4, h >= 2: 1 + 2*f(h-1, 2) = 1 + 2*(1 + 2(h-1)) = 1 + 2 + 4(h-1) = 3 + 4h - 4 = 4h - 1. // Pattern: f(h, m) = m*h - m + 1 + (m-1) = mh - m + m = mh? No that doesn't match. // f(h,1) = h+1. f(h,2)=2h+1-1=2h+1? No, 1+2h. Hmm. // f(1,1) = 2. f(1,2) = 3. // f(2,1) = 3. f(2,2) = 1+2*2 = 5. f(2,3) = 1+2+3 = 6. f(2,4) = 1+2*3 = 7 = 2^3 - 1. // For m = 2^h: f(h, 2^h) = 2^(h+1) - 1 (all nodes activated). // General formula: in a perfect binary tree of height h, selecting m leaves to maximize activated nodes. // Let g(h, m) = max #activated nodes. // g(h, m) = 1 + max over valid (m1,m2) of (g(h-1,m1) + g(h-1,m2)) for m >= 1 // where m1+m2=m, 0<=m1,m2<=2^(h-1), and we define g(h-1,0)=0. // The optimal strategy: split as evenly as possible. // g(h, m): we can think level by level. At depth 0 (root): 1 node activated. // At depth 1: min(m, 2) nodes activated. // At depth 2: min(m, 4) nodes activated. // ... // At depth h: m nodes activated (leaves). // Total: sum_{i=0}^{h} min(m, 2^i). // Let me verify: g(2, 3) = min(3,1) + min(3,2) + min(3,4) = 1+2+3 = 6. ✓ // g(2, 2) = 1+2+2 = 5. ✓ // g(2, 1) = 1+1+1 = 3. ✓ // g(1, 1) = 1+1 = 2. ✓ // g(1, 2) = 1+2 = 3. ✓ // Great! So g(h, m) = sum_{i=0}^{h} min(m, 2^i). // Now, back to our problem. We need to collect all the "pieces" (subtrees and path segments) // and figure out the optimal allocation of k strings. // The structure: // Common prefix: s[0..lcp-1]. For depths 1..lcp, there's exactly 1 node, always activated. // At depth lcp, s and t diverge. s[lcp]='a', t[lcp]='b'. // // Left branch (s-side): node at depth lcp+1 corresponding to prefix s[0..lcp]+'a'... wait, s[0..lcp] is s[0..lcp-1] + s[lcp] = s[0..lcp-1] + 'a'. // But actually the branching happens at the node at depth lcp (the end of common prefix). // Its left child corresponds to ...+'a' and right child to ...+'b'. // s continues to the left child, t continues to the right child. // Let me re-index: depth d means prefix of length d. // The LCP node is at depth lcp. Its two children are at depth lcp+1. // s goes to the left child (s[lcp]='a'), t goes to the right child (t[lcp]='b'). // s-side path: from depth lcp+1 down to depth n. // At each depth d (lcp+1 <= d <= n-1), we're at a node on the s-boundary. // The s-path continues to the child indicated by s[d]. // The OTHER child is either: // - A full subtree of height (n - d - 1) if s[d] = 'a' (other child is 'b' side, all >= s) // - Empty (0 available) if s[d] = 'b' (other child is 'a' side, all < s) // Wait, this needs more care. At depth d on the s-boundary, we're looking at the node // that corresponds to the prefix s[0..d-1]. If s[d]='a', we go left. // The right child has prefix s[0..d-1]+'b'. All strings with this prefix are > s (since s goes left here). // Also we need to check they are <= t. Since we're on the s-side (left branch from lcp), // the right child subtree: its prefix is s[0..lcp-1]+'a'+...+'b'. // At depth lcp, we went left (to 'a'). Anything in this left branch with the same prefix up to depth d-1 // but going right at depth d: is it <= t? t starts with s[0..lcp-1]+'b'..., // and our string starts with s[0..lcp-1]+'a'..., so yes, it's < t because 'a' < 'b' at position lcp. // So the right child subtree is fully available with 2^(n-d-1) leaves. // If s[d]='b', the other child (left/'a') has prefix s[0..d-1]+'a'. // All strings with this prefix are < s[0..d] since at position d they have 'a' < 'b' = s[d]. // But we also need >= s. Since s[0..d-1] matches but s[d]='b' and these have 'a' at position d, // these strings are < s. So 0 available. The left child is empty. // Similarly at depth n (leaf): the s-path leaf is string s itself. It's available (1 leaf). // t-side path: from depth lcp+1 down to depth n. // At each depth d (lcp+1 <= d <= n-1), on the t-boundary: // If t[d]='b', we go right. The left child ('a' side) is fully available with 2^(n-d-1) leaves. // (These are all <= t because t goes right, and they're all >= s because they're in the right branch at depth lcp.) // If t[d]='a', the right child ('b' side): all strings there are > t. 0 available. // At depth n: t-path leaf is string t, available (1 leaf). // So the pieces are: // Path pieces (always contribute their count to answer if activated): // - Common prefix: lcp nodes // - s-branch: n - lcp nodes on the s-path (depths lcp+1 to n) // - t-branch: n - lcp nodes on the t-path (depths lcp+1 to n) // But some path nodes might not be activated if we don't pick any string in their subtree. // Free subtrees along s-path (when s[d]='a' for lcp+1 <= d <= n-1... wait, d should start from lcp): // Hmm, let me re-examine. The s-path goes from depth lcp+1 to depth n. // At each internal node on the s-path (depths lcp+1 to n-1), one child continues the s-path, // the other child is either a free subtree or empty. // Actually, the node at depth lcp+1 has its parent at depth lcp. The branching at depth lcp // is handled by the "at depth lcp, s goes left, t goes right" split. So the s-path starts at the // left child of the lcp node, which is at depth lcp+1. // More precisely: // For d from lcp to n-1: // If d == lcp: the node at depth lcp branches: left child -> s-path, right child -> t-path. // If d > lcp and d <= n-1 on the s-path: // The node at depth d on the s-path: // If s[d] == 'a': right child is a free full subtree of height (n - d - 1). // If s[d] == 'b': left child is empty. // s-path continues to the child indicated by s[d]. // Similar for t-path for d from lcp+1 to n-1... wait, let me be more careful. // Let's define: // s_subtrees: list of (height) of free subtrees along s-boundary // t_subtrees: list of (height) of free subtrees along t-boundary // For the s-boundary, at each depth d from lcp+1 to n-1 (these are internal nodes on the s-path): // Node at depth d is on the s-path. // Its children are at depth d+1. // s[d] tells us which child the s-path continues to. // If s[d] == 'a': the other child (right/'b') is a free subtree of height n-(d+1) = n-d-1. // This subtree has 2^(n-d-1) leaves. // If s[d] == 'b': the other child is empty. // Wait, I think there's an off-by-one. Let me re-examine. // The s-path at depth lcp+1: this is the node with prefix s[0..lcp]. // Actually, prefix of length lcp+1, which is s[0..lcp] (0-indexed). // Then from this node, at position lcp+1 (0-indexed) in the string, we look at s[lcp+1] to decide which child. // So for d from lcp+1 to n-1: // At the s-path node at depth d (prefix = s[0..d-1]): // We look at s[d] to decide next step. // If s[d] == 'a': free subtree on the right with height n - (d+1) = n-d-1. // If s[d] == 'b': nothing on the left. // At depth n (leaf s), it's just one string. // Similarly for t-boundary, at each depth d from lcp+1 to n-1: // If t[d] == 'b': free subtree on the left with height n-d-1. // If t[d] == 'a': nothing. // Now, the plan: // We want to choose k strings (with repetition not allowed, since each string is distinct) // from the available set [s, t]. // Total available strings = (binary number t) - (binary number s) + 1. But this could be huge. // However, k <= 10^9 and n can be 5*10^5. // The answer = number of activated trie nodes = number of distinct prefixes of length 1..n. // To maximize activated nodes, we should think greedily: // 1. We must use at least 1 string. This activates one root-to-leaf path. // 2. Each additional string can be chosen to maximize new activated nodes. // But with the structure we have, let's think of it as: // The trie paths form a "Y" shape (common prefix + two branches). // Along each branch, there are free subtrees hanging off. // If we pick 1 string from s-branch and 1 from t-branch, we activate: // lcp (common prefix) + (n-lcp) (s-branch path) + (n-lcp) (t-branch path) = 2n - lcp nodes from paths alone. // But we might not have 2 strings (k=1), or both branches might have strings available. // Wait, actually both branches always have at least 1 string each (s is in the s-branch, t is in the t-branch). // Unless s == t, which we handled above. // So if k >= 2, we can always activate both branches. // If k == 1, we pick one string which activates n nodes (one root-to-leaf path). // OK so let me think about this more carefully. // Let's collect all the free subtrees. For each free subtree, we know its height h. // It has 2^h leaves. If we send m strings through it, it contributes g(h, m) = sum_{i=0}^{h} min(m, 2^i) nodes. // The "path" nodes are: common prefix (lcp nodes) + s-branch path (n-lcp nodes) + t-branch path (n-lcp nodes). // But some of these path nodes are only activated if we send strings through them. // Actually, let's think of it as: we have a tree structure. // Root (depth 0) -> common prefix path down to depth lcp -> branches to s-side (depth lcp+1) and t-side (depth lcp+1). // Along s-side: nodes at depths lcp+1, ..., n. From some of these nodes, free subtrees branch off. // Along t-side: similarly. // The leaf at the end of s-path is string s (1 available leaf). // The leaf at the end of t-path is string t (1 available leaf). // Each free subtree has some number of available leaves. // Now, the answer is: we pick k leaves total, and count how many tree nodes have at least one // selected leaf as descendant. // The tree looks like: // [common prefix: lcp edges, lcp+1 nodes including root] // / \ // [s-path from depth lcp+1] [t-path from depth lcp+1] // at each node, possibly a free subtree similarly // ends at leaf s ends at leaf t // If we select at least 1 leaf from the s-side, all s-path nodes are activated? No! // Only the nodes on the s-path from depth lcp+1 down to the deepest activated node on that side. // Hmm, actually the s-path from depth lcp+1 to depth n is a chain, and any string that starts // with the s-boundary prefix up to some depth d is a descendant of the s-path node at depth d. // But a string from a free subtree branching off at depth d is a descendant of the s-path node // at depth d but NOT of the s-path node at depth d+1. // So the s-path nodes from depth lcp+1 to depth d are activated if any leaf from the s-side // at depth >= d (along the s-path or from a subtree branching at depth >= d) is selected. // Hmm, this is getting complex. Let me think of it differently. // Let me consider the two sides separately. // For the s-side, the structure is: // A path from depth lcp+1 to depth n (that's n - lcp nodes). // At certain depths along this path, there are subtrees branching off to the side. // The leaf at the end of the path is string s itself (1 leaf). // For the s-side, if we allocate m strings to it (m >= 0), the maximum number of // activated nodes ON THE S-SIDE (depths lcp+1 to n) is some function of m. // Similarly for the t-side. // Plus, if we allocate m_s >= 1 and m_t >= 1, the common prefix contributes lcp nodes. // If only one side is used, the common prefix still contributes lcp nodes (the path from root to depth lcp). // If 0 strings used: answer = 0, but k >= 1 so this doesn't happen. // Wait, if we use only the s-side, the common prefix is depths 1..lcp, and the s-side is lcp+1..n. // We activate depths 1..lcp (lcp nodes) plus whatever on the s-side. // If we use both sides, we activate lcp nodes for common prefix plus s-side contribution plus t-side contribution. // But there's also depth 0 (the root, empty prefix). The problem says "prefixes of at least one of the written strings", and the empty string is a prefix of every string. But wait, is the empty string counted? Let me re-read. // "the number of strings that are prefixes of at least one of the written strings" // The empty string is a prefix of every string, so it's always counted if k >= 1. // But wait, do we count strings of length 0? The problem says "k strings of length n", and // prefixes of a string of length n have lengths 0, 1, ..., n. So there are n+1 prefixes including // the empty string. But examples: // Example 1: n=2, k=4, s="aa", t="bb". // All 4 strings: aa, ab, ba, bb. Prefixes: "", a, b, aa, ab, ba, bb = 7? // But the answer is 6. So the empty string is NOT counted, or the problem counts prefixes of // length 1 to n only. Let me re-read. // "c — the number of strings that are prefixes of at least one of the written strings" // "" is a prefix of every string, so it should be counted. But the answer is 6 for example 1. // Prefixes of lengths 1 and 2: a, b (length 1), aa, ab, ba, bb (length 2) = 6. So empty string not counted. // Actually I think "strings" here means non-empty strings. Or maybe the empty string is not // considered a "string" in this context. The answer matches if we count prefixes of lengths 1..n. // OK so we count prefixes of lengths 1 through n. The trie has nodes at depths 1..n (n depths). // This is the same as what I had before (the root at depth 0 is not counted). // Now, let me define the contribution of each side. // For the s-side, with allocation m (number of strings from s-side): // f_s(m) = max number of activated nodes at depths lcp+1 to n on the s-side. // Similarly f_t(m) for the t-side. // Answer = lcp + f_s(m_s) + f_t(m_t) where m_s + m_t = k, m_s >= 0, m_t >= 0, // m_s <= total_s (total available on s-side), m_t <= total_t (total available on t-side). // But also we need m_s + m_t <= total_s + total_t and m_s + m_t = min(k, total_s + total_t). // Actually, the lcp contribution: if m_s + m_t >= 1, the common prefix (lcp nodes) is activated. // Since k >= 1, this is always true unless... well, there's always at least s and t available. // Wait, s == t case is handled. So lcp contribution = lcp always (since k >= 1). // Wait, but the common prefix should be activated only if at least one string passes through it. // Since k >= 1 and there exist strings in [s,t], yes, it's always activated. // Hmm, but what about the node at depth lcp+1 on the s-side? It's only activated if m_s >= 1. // And nodes below it on the s-path are activated only if we send strings through them. // Let me think about f_s(m) more carefully. // The s-side structure (as a chain with hanging subtrees): // Let me list the "components" along the s-path from top to bottom. // Node at depth lcp+1 (call it the s-root). // Node at depth lcp+2, ..., node at depth n (leaf s). // At each depth d (lcp+1 <= d <= n-1), there might be a free subtree hanging off. // The free subtree at depth d branches off at the child NOT on the s-path. // Its root is at depth d+1. Its height is n - (d+1) = n - d - 1. // It has 2^(n-d-1) leaves. // Now, f_s(m): // If m = 0: 0. // If m >= 1: we must activate the s-path down to wherever our deepest string is. // Essentially, the s-side is a caterpillar tree. The main path has n-lcp nodes (depths lcp+1 to n). // Hanging off this path at certain depths are full subtrees. // To maximize activated nodes with m strings: // Optimal strategy: first, pick 1 string = s itself. This activates the entire s-path (n-lcp nodes). // Cost: 1 string. Benefit: n-lcp nodes. // Then, with each remaining string, pick from the free subtrees to maximize gain. // OR, don't pick s and instead use free subtrees, but then you might not activate the full path. // Actually, the deepest free subtree is closest to the leaf, and the shallowest is closest to the s-root. // If we pick a string from a free subtree at depth d (branching off at depth d, subtree root at depth d+1): // - It activates the s-path from depth lcp+1 to depth d (d - lcp nodes). // - Plus the activated nodes in the subtree (height n-d-1). // - Plus if we also pick strings from subtrees at deeper depths, they activate more of the path. // The key insight: if we pick string s itself, the entire path is activated (n-lcp nodes), and then // free subtrees only need to contribute their internal nodes. Each additional string from a free subtree // of height h adds g(h, m) nodes to the existing path. // But if we DON'T pick string s, we might save that 1 string budget and use it elsewhere. // However, string s activates n-lcp path nodes which is a lot. // Hmm, this is getting complicated. Let me think about it as a tree DP problem but in a smart way. // Actually, I think the best approach is: // Observation: The trie structure relevant to [s,t] has O(n) nodes of interest. // We want to choose k leaves to maximize the number of activated internal nodes. // Greedy approach: picking the first string (from either side) gives n new prefixes. // Picking a second string that diverges from the first as early as possible gives the most new prefixes. // The idea of a "greedy" approach: at each step, pick the string that adds the most new prefixes. // But k can be up to 10^9, so we need to batch these. // Alternative cleaner approach: // Total answer = lcp + contribution_s(m_s) + contribution_t(m_t) // where m_s + m_t = min(k, total_available), m_s <= cap_s, m_t <= cap_t. // We want to maximize the sum. // For each side, the contribution function is concave (each additional string gives diminishing returns). // So the optimal split can be found, e.g., by finding where the marginal gains cross. // But computing contribution_s(m) for arbitrary m is itself non-trivial. // Let me think about contribution_s(m) more carefully. // The s-side is like a main path of length n-lcp (nodes at depths lcp+1, ..., n). // At some positions along this path, full binary subtrees branch off. // Let's say the subtrees branch off at depths d_1 < d_2 < ... < d_r (on the s-side). // Each subtree at depth d_i has height h_i = n - d_i - 1 and capacity 2^(h_i) leaves. // Also there's the leaf s at depth n (capacity 1, height 0 essentially). // When we pick m strings from the s-side: // Some go to the leaf s, some go to the various subtrees. // Each subtree at depth d_i, if we send m_i strings to it, contributes g(h_i, m_i) nodes. // But we also need to count the path nodes that are activated. // A path node at depth d is activated if any string we picked has depth >= d. // i.e., if any subtree at depth >= d or the leaf s gets at least 1 string. // Let's define the path contribution: if the "deepest" allocation is at depth d_max, // then path nodes from lcp+1 to d_max are activated. But it's not just the deepest; // all path nodes up to the deepest active point are activated. // Wait, any string passing through the s-path must pass through all path nodes from lcp+1 // down to whatever depth it branches off. So path node at depth d is activated iff there exists // a selected string that passes through it, which means a string from a subtree at depth >= d // or string s itself (which passes through all path nodes). // Hmm, actually the subtree at depth d_i branches off at the node at depth d_i. The subtree root // is a child of the path node at depth d_i. So a string in that subtree passes through path nodes // at depths lcp+1, lcp+2, ..., d_i. And then goes into the subtree (not continuing along the s-path). // Wait, I need to be more precise. The s-path node at depth d has prefix s[0..d-1]. Its two children: // one continues the s-path (prefix s[0..d]), and the other is the free subtree root (if available). // A string in the free subtree at depth d passes through the s-path from depth lcp+1 to depth d, // then goes to the free subtree child at depth d+1. // The s-path node at depth d+1 is NOT activated by this string (it goes to the other child). // So the path contribution: depth d on the s-path (lcp+1 <= d <= n) is activated iff there's a // selected string from a subtree at depth d' >= d on the s-path, or from the s-leaf. // I.e., sum of allocations to subtrees at depths >= d plus allocation to s-leaf is >= 1. // Let me re-index. Let the branching points on the s-side be at depths lcp+1 <= d_1 < d_2 < ... < d_r <= n-1. // (These are the depths where s[d_i] = 'a', so a free subtree branches to the right.) // At depth d_i, the free subtree has height h_i = n - d_i - 1, capacity cap_i = 2^h_i. // Also there's the s-leaf at depth n, capacity 1 (this is string s itself). // Now, path nodes: depths lcp+1, lcp+2, ..., n. Each needs at least one string "passing through" // it to be activated. // A string from the subtree at d_i passes through path nodes lcp+1, ..., d_i. // The s-leaf passes through all path nodes lcp+1, ..., n. // So path node at depth d is activated iff: // (allocation to s-leaf >= 1) OR (allocation to any subtree at depth d' >= d is >= 1) // = (total allocation to subtrees at depths >= d + s-leaf allocation >= 1). // Hmm, this is like: the path has segments. Between branching points, there are "segments" of path // that are only activated by strings from deeper branching points or the s-leaf. // Let me order the components from shallowest to deepest: // Subtree at d_1 (shallowest), ..., subtree at d_r, s-leaf at depth n (deepest). // Define the "cost" of using a component: how many additional path nodes does it activate // beyond what's already activated by deeper components? // This is exactly the number of path nodes between this component and the next deeper component. // If we think of it bottom-up: // The s-leaf at depth n: using it activates path nodes from n down to (last subtree's depth + 1)... // Actually, let me think top-down. // Imagine we decide which components to "activate" (send at least 1 string to). // The set of activated path nodes is the union of {lcp+1, ..., d_i} for each activated component i, // and {lcp+1, ..., n} if s-leaf is activated. // = {lcp+1, ..., max(activated component depths, n if s-leaf activated)}. // Because the path is a chain and components at shallower depths activate a subset of what // deeper ones activate. // So the path contribution is: max_depth - lcp, where max_depth is the maximum depth among // activated components (using depth n for s-leaf, depth d_i for subtree i). // And the subtree contribution is sum of g(h_i, m_i) for activated subtrees (m_i >= 1). // Plus the s-leaf contributes 1 node (depth n) if activated... wait, the path already includes depth n. // Actually, the leaf node at depth n IS a path node. So the s-leaf being activated means // the path is fully activated (n - lcp nodes) and the leaf node is one of them. // For a subtree at depth d_i, its root is at depth d_i + 1 (a child of the path node at d_i). // The nodes in the subtree are at depths d_i+1 to n. These are NOT path nodes; they're in the subtree. // If we send m_i strings to this subtree, it contributes g(h_i, m_i) nodes (including the subtree root). // So total contribution from s-side = (path nodes activated) + sum(subtree nodes activated). // Path nodes activated = max_depth - lcp, where max_depth = max of all activated component depths // (d_i for subtree i, n for s-leaf). // Subtree nodes activated = sum_{i activated} g(h_i, m_i). // Hmm wait, I'm double-counting. Let me be very precise. // The trie nodes on the s-side are: // 1. Path nodes: depths lcp+1, lcp+2, ..., n. These are the nodes with prefixes s[0..lcp], s[0..lcp+1], ..., s[0..n-1]. // 2. Subtree nodes: for each branching point d_i, the subtree root is at depth d_i+1 (it's the NON-s-path child of the path node at depth d_i). The subtree spans depths d_i+1 to n. // A selected string from subtree i passes through path nodes lcp+1, ..., d_i, then the subtree root at depth d_i+1, and then further into the subtree. // The s-leaf is the path node at depth n. A string that is exactly s passes through all path nodes. // So: // - Path node at depth d (lcp+1 <= d <= n) is activated iff at least one selected string passes through it. // A string from subtree i passes through path node at depth d iff d <= d_i. // The string s passes through all path nodes. // So path node at depth d is activated iff (s is selected) OR (some subtree i with d_i >= d has m_i >= 1). // - Subtree internal node is activated iff at least one selected string passes through it. // This is determined by the allocation within the subtree. // So the number of activated path nodes: // = |{d : lcp+1 <= d <= n, d is activated}| // If s is selected or some subtree with d_i >= d exists and has m_i >= 1: // Let D = max d_i among activated subtrees (d_i of subtrees with m_i >= 1), or lcp if no subtree is activated. // If s is selected: all n - lcp path nodes are activated. // Else: D - lcp path nodes are activated (depths lcp+1, ..., D). // Number of activated subtree nodes: // For subtree i with allocation m_i >= 1: g(h_i, m_i) nodes. // (This counts the subtree root and all nodes inside the subtree.) // g(h_i, m_i) = sum_{j=0}^{h_i} min(m_i, 2^j). // The subtree has height h_i = n - d_i - 1, and its nodes are at depths d_i+1 to n. // So it has h_i + 1 levels (depths d_i+1, ..., n), with 1, 2, 4, ..., 2^{h_i} nodes at each level. // Selecting m_i leaves activates min(m_i, 2^j) nodes at the j-th level from the root. // g(h_i, m_i) = sum_{j=0}^{h_i} min(m_i, 2^j). This is correct. // And the s-leaf doesn't contribute any subtree nodes (it's a path node). // OK so now, for the s-side, given m strings to allocate: // We want to maximize: // (activated path nodes) + sum_i g(h_i, m_i) // subject to: // sum_i m_i + (1 if s selected) <= m // m_i >= 0 for all i, m_i <= cap_i // s selected is 0 or 1, if selected it uses 1 string // Actually, the s-leaf is just one specific leaf. Selecting it means using 1 out of the m budget. // It activates all path nodes (contribution: n - lcp) but doesn't add any subtree nodes. // If we select s, path nodes = n - lcp, and we have m - 1 strings left for subtrees. // If we don't select s, path nodes = D - lcp (where D is the max depth of an active subtree), // and we have m strings for subtrees. // Hmm, this is a complex optimization. Let me think of an alternative approach. // Alternative approach: think of the problem as maximizing the total "value" where each trie node // has value 1 if at least one selected leaf is its descendant. // The trie structure for [s, t]: // - Common prefix path: lcp nodes. // - Two branches. // - Each branch is a chain with hanging full subtrees. // Total number of "interesting" subtrees is O(n). // KEY INSIGHT: In a full binary subtree of height h, the marginal gain of the k-th string is: // g(h, k) - g(h, k-1). // g(h, k) = sum_{j=0}^{h} min(k, 2^j). // g(h, k) - g(h, k-1) = sum_{j=0}^{h} (min(k, 2^j) - min(k-1, 2^j)) = |{j : 2^j >= k}|. // = number of j in [0, h] such that 2^j >= k. // = max(0, h + 1 - floor(log2(k))) if k >= 1. More precisely: // = max(0, h + 1 - ceil(log2(k+1)) + 1)... let me just compute it properly. // min(k, 2^j) - min(k-1, 2^j) = 1 if 2^j >= k, else 0. // So the marginal gain is |{j : 0 <= j <= h, 2^j >= k}|. // = |{j : j >= ceil(log2(k)), j <= h}|. // = max(0, h - ceil(log2(k)) + 1) if k >= 1. // When k = 1: ceil(log2(1)) = 0, so gain = h + 1. // When k = 2: ceil(log2(2)) = 1, so gain = h. // When k = 3: ceil(log2(3)) = 2, gain = max(0, h - 1). // When k = 4: ceil(log2(4)) = 2, gain = max(0, h - 1). // When k = 5: ceil(log2(5)) = 3, gain = max(0, h - 2). // So the marginal gain is non-increasing (concave). Good. // Now, the problem is: we have a set of subtrees (and some structural path nodes). // We want to distribute k strings among the subtrees to maximize the total contribution. // Because each subtree's contribution is concave, the overall problem is to distribute k items // among concave functions to maximize the sum. This is solved by repeatedly picking the subtree // with the highest marginal gain. // But we also need to handle the path activation. This complicates things because the path // contribution depends on which subtrees are activated and how deep they are. // Let me rethink. // Actually, I think there's a much cleaner way to view this. // Let me consider the whole trie (not just one side). // The relevant trie has: // - A common prefix path of length lcp. // - From the LCP node, left branch to s-side, right branch to t-side. // - s-side: a chain from depth lcp+1 to n, with subtrees hanging off where s[d]='a'. // - t-side: a chain from depth lcp+1 to n, with subtrees hanging off where t[d]='b'. // Now, think of the FULL answer as: pick k leaves, maximize activated trie nodes. // Let me introduce a new concept: "the cost of adding a leaf to an empty set" is n (activates n nodes). // The cost of adding a second leaf that diverges at depth d from all existing leaves is (n - d). // In general, each new leaf adds (n - d) nodes, where d is the depth of the LCA with all existing leaves. // Wait, more precisely, (n - d) new nodes where d is the max depth at which this leaf's prefix // matches any already-activated prefix. Hmm, not exactly. The new leaf adds all nodes on its // root-to-leaf path that are not yet activated. If it diverges from the current set of activated // paths at depth d, it adds n - d new nodes. // But "diverges at depth d" means: the path node at depth d is already activated, but the child // node at depth d+1 on this new leaf's path is NOT activated. So the new leaf adds nodes at // depths d+1, ..., n, which is n - d new nodes. // For the new leaf in a subtree at depth d_i on the s-side: it diverges from the s-path at depth d_i. // If the subtree is already activated (has some strings in it), the new leaf diverges deeper // (within the subtree). // This is getting complicated. Let me try a different approach. // Approach: compute the answer by considering the trie structure. // The key observation: the trie is a tree, and the answer is the number of nodes (at depths 1..n) // with at least one selected descendant leaf. This equals the sum over all edges (or nodes // excluding root) of the indicator that the subtree below has a selected leaf. // Equivalently, for each trie node v at depth d (1 <= d <= n), let A(v) = number of available leaves // in its subtree. We want to place k "selections" on leaves (each leaf can be selected at most once), // and the answer is the number of nodes v (depth 1 to n) with at least one selected leaf in their subtree. // To maximize this, we use the greedy algorithm: // sort all internal nodes by A(v) (or rather, process them in a way that greedily maximizes activations). // Alternative clean observation: // Answer = sum_{d=1}^{n} (number of distinct prefixes of length d among selected strings). // For each depth d, the number of distinct prefixes of length d = number of nodes at depth d // with at least one selected descendant. // At depth d, the nodes with at least one available leaf are the relevant ones. // At each depth d, we want to maximize the number of distinct depth-d prefixes. // This is min(k, #nodes at depth d with available leaves). // Wait, is this correct? If we have k strings, we have at most k distinct prefixes at each depth. // And we have at most (number of nodes with available leaves) distinct prefixes. // So at depth d, the contribution is min(k, c_d) where c_d = number of trie nodes at depth d // that have at least one leaf in [s, t] as a descendant. // AND we need to check that there exists a selection of k strings achieving all these minima simultaneously. // This is a key question: is it always possible to achieve min(k, c_d) at every depth simultaneously? // The answer is YES! Here's why: // The values c_d form a non-decreasing then eventually non-increasing sequence? Actually, c_d // could be arbitrary. But: c_d is the number of nodes at depth d with at least one [s,t]-leaf descendant. // As d increases, each node at depth d is a child of a node at depth d-1. So c_d <= 2 * c_{d-1}. // Also, a node at depth d-1 with at least one available leaf must have at least one child at depth d // with an available leaf. So c_d >= c_{d-1}. // Actually c_d >= c_{d-1} and c_d <= 2 * c_{d-1}. // And the total available leaves = c_n (each leaf is a trie node at depth n with exactly itself). // So c_n = total number of strings in [s, t]. // Now, can we always achieve min(k, c_d) at all depths simultaneously? // We want to pick k leaves (from c_n available) such that at each depth d, the number of distinct // depth-d prefixes is min(k, c_d). // Consider: pick k leaves to maximize the number of distinct depth-1 prefixes. We achieve min(k, c_1). // Among all such selections, maximize depth-2 prefixes, etc. This greedy layered approach would work // if at each layer, the constraint from the previous layer doesn't prevent us from achieving the optimum. // Actually, I believe the answer is indeed sum_{d=1}^{n} min(k, c_d). // This is because the trie is a tree, and we can always find a selection of k leaves that // simultaneously maximizes the spread at every depth. // Proof sketch: Take any k leaves. At depth d, they determine at most k distinct prefixes // out of c_d possible. Now, if some depth has fewer than min(k, c_d) distinct prefixes, // we can swap some leaf to increase it without decreasing other depths. This is because // at depth d, if we use only q < min(k, c_d) distinct prefixes, some node at depth d with // available leaves is unused. We can take one of our leaves from a node at depth d that has // multiple selected leaves and move one to the unused node. This doesn't decrease the number // of distinct prefixes at any depth <= d (the moved leaf might decrease count at its old node // but it was >=2 so it stays activated, and the new node becomes activated). At depth d, we // gain 1. At depths > d, the situation might change but won't get worse in an appropriate // selection. // Hmm, actually this argument is incomplete. At depths > d, moving a leaf from one subtree to // another could change things. But the key insight is: // In a tree, the sum of min(k, c_d) is achievable. // This is actually a well-known result. In a binary tree, if you pick k leaves, the number // of ancestors is sum_{d} min(k, c_d) where c_d is the number of nodes at depth d with at // least one leaf. This holds when k <= total leaves and the tree has a specific structure. // Wait, let me verify with example 2 from the problem: // n=3, k=3, s="aba", t="bba" // Strings in [aba, bba]: aba, abb, baa, bab, bba. That's 5 strings. // k=3, answer should be 8 (from the note, he writes "aba", "baa", "bba"). // Prefixes of these 3 strings: // Length 1: a, b -> 2 distinct // Length 2: ab, ba, bb -> 3 distinct // Length 3: aba, baa, bba -> 3 distinct // Total: 2 + 3 + 3 = 8. ✓ // Now, c_1 = number of depth-1 nodes with available leaves. Depth-1 nodes: 'a' and 'b'. // 'a' has leaves aba, abb -> available. 'b' has leaves baa, bab, bba -> available. // c_1 = 2. // c_2 = depth-2 nodes: aa (leaves: aaa, aab -> not in range), ab (aba, abb -> yes), // ba (baa, bab -> yes), bb (bba, bbb; bba is in range, bbb... is bbb > bba? yes. so bbb not in range. bb -> bba available). // Actually wait: strings in [aba, bba] of length 3: aba, abb, baa, bab, bba. // c_2: // ab -> has aba, abb (in range) -> yes // ba -> has baa, bab (in range) -> yes // bb -> has bba (in range) -> yes // aa -> has aaa, aab (not in range, since aab < aba) -> no // c_2 = 3. // c_3 = 5 (all 5 strings). // min(3, c_1) + min(3, c_2) + min(3, c_3) = 2 + 3 + 3 = 8. ✓ // Let me verify example 1: n=2, k=4, s="aa", t="bb". // All 4 strings available. c_1 = 2, c_2 = 4. // min(4, 2) + min(4, 4) = 2 + 4 = 6. ✓ // Great! So the answer is sum_{d=1}^{n} min(k, c_d). // Now I need to compute c_d for each depth d from 1 to n. // c_d = number of binary strings of length d that are prefixes of at least one string in [s, t]. // A string p of length d is a prefix of some string in [s, t] iff: // there exists a string x of length n with prefix p such that s <= x <= t. // This is equivalent to: the lexicographically smallest string with prefix p is <= t, // AND the lexicographically largest string with prefix p is >= s. // Smallest with prefix p: p followed by (n-d) 'a's. // Largest with prefix p: p followed by (n-d) 'b's. // So: p + "aa...a" <= t AND p + "bb...b" >= s. // Equivalently: p + "aa...a" <= t[0..n-1] AND p + "bb...b" >= s[0..n-1]. // How many strings p of length d satisfy this? // c_d = |{p of length d : p + "a"^(n-d) <= t AND p + "b"^(n-d) >= s}| // Let me denote: // For the condition p + "a"^(n-d) <= t: // Compare p with t[0..d-1]. // If p < t[0..d-1]: condition satisfied. // If p > t[0..d-1]: condition not satisfied. // If p == t[0..d-1]: then "a"^(n-d) <= t[d..n-1], which is always true (since "a"^(n-d) is the smallest). // So condition is: p <= t[0..d-1]. // Wait, is that right? p + "aa...a" <= t. If p < t[0..d-1] (lexicographically), then // p + "aa...a" < t[0..d-1] + anything, so p + "aa...a" <= t. Yes. // If p = t[0..d-1], then p + "aa...a" <= t iff "aa...a" <= t[d..n-1], which is true. Yes. // If p > t[0..d-1], then p + "aa...a" > t[0..d-1] + anything >= t. So condition fails. // So the condition is simply p <= t[0..d-1]. // Similarly, p + "b"^(n-d) >= s: // If p > s[0..d-1]: condition satisfied. // If p < s[0..d-1]: condition not satisfied. // If p == s[0..d-1]: then "b"^(n-d) >= s[d..n-1], which is always true. // So condition is: p >= s[0..d-1]. // Therefore: c_d = |{p of length d : s[0..d-1] <= p <= t[0..d-1]}| // = (binary value of t[0..d-1]) - (binary value of s[0..d-1]) + 1. // But these are binary strings where 'a' = 0 and 'b' = 1. The number of strings from s[0..d-1] to t[0..d-1] // is just the numeric difference + 1. // But d can be up to 5*10^5, so these are big numbers. We need min(k, c_d) for each d. // k can be up to 10^9. // c_d = val(t[0..d-1]) - val(s[0..d-1]) + 1 where val converts binary string to number. // We need min(k, c_d) = min(k, val(t[0..d-1]) - val(s[0..d-1]) + 1). // Note: c_d >= 1 always (since s <= t implies s[0..d-1] <= t[0..d-1]). // Actually, wait: s[0..d-1] could equal t[0..d-1] for d <= lcp. In that case c_d = 1. // For d > lcp: s[0..d-1] < t[0..d-1], so c_d >= 2. // Also, c_d <= 2^d. // For d <= lcp: c_d = 1, so min(k, c_d) = 1. // Total contribution from d=1..lcp: lcp. // For d > lcp: c_d = val(t[0..d-1]) - val(s[0..d-1]) + 1. // Let me compute this incrementally. // val(t[0..d-1]) = 2 * val(t[0..d-2]) + (t[d-1] == 'b' ? 1 : 0). // val(s[0..d-1]) = 2 * val(s[0..d-2]) + (s[d-1] == 'b' ? 1 : 0). // diff_d = val(t[0..d-1]) - val(s[0..d-1]) = 2 * diff_{d-1} + (t[d-1] - s[d-1]). // where t[d-1] and s[d-1] are 0 or 1. // c_d = diff_d + 1. // min(k, c_d) = min(k, diff_d + 1). // Since diff_d can grow exponentially (up to 2^d), we need to handle it carefully. // When diff_d >= k, min(k, diff_d + 1) = k. So once diff_d >= k, all subsequent depths also give k. // Since diff_d doubles (roughly) each step, it will exceed k within about log2(k) steps after lcp. // Since k <= 10^9, this is about 30 steps. After that, all depths contribute k. // So the algorithm: // 1. Compute lcp. Contribution from d=1..lcp: lcp. // 2. For d = lcp+1, lcp+2, ..., track diff_d = 2 * diff_{d-1} + (t[d-1] - s[d-1]). // (Using 0 for 'a', 1 for 'b'.) Start with diff_lcp = 0 (since s[0..lcp-1] = t[0..lcp-1]). // Wait, at d = lcp+1: diff_{lcp+1} = 2 * diff_lcp + (t[lcp] - s[lcp]) = 0 + (1 - 0) = 1. // c_{lcp+1} = 2. // 3. While diff_d < k and d <= n, add min(k, diff_d + 1) to the answer and increment d. // 4. Once diff_d >= k (or equivalently diff_d + 1 >= k, i.e., c_d >= k), the remaining depths // all contribute k. So add k * (n - d + 1) to the answer. Wait, we're at depth d already computed, // and remaining is d+1 to n. Hmm, let me be careful. // Let me code this up. // Initialize: // answer = lcp (from depths 1 to lcp) // diff = 0 (this is diff_lcp) // For d = lcp+1 to n: // td = 0 if t[d-1] == 'a', else 1 (0-indexed: t[d-1]) // sd = 0 if s[d-1] == 'a', else 1 // diff = 2 * diff + (td - sd) // if diff + 1 >= k: // answer += k // // all subsequent depths also have c_d >= k since diff only grows // // so answer += k * (n - d) for depths d+1 to n // // but we already added k for depth d // answer += k * (n - d) // for the remaining depths // break // else: // answer += diff + 1 // (if we reach d = n without breaking, that's fine) // Wait, but diff can be huge. Since we break once diff >= k-1, and diff starts at 0 and // roughly doubles each step, it takes about 30 steps. So diff stays manageable (< 2 * 10^9 or so). // But actually diff = 2 * diff + delta where delta is -1, 0, or 1. So diff could be negative? // No: diff_d = val(t[0..d-1]) - val(s[0..d-1]) and since s <= t, s[0..d-1] <= t[0..d-1] // (as binary numbers)... wait is that true? // // If s < t lexicographically, it's possible that s[0..d-1] > t[0..d-1] for some d? // No! s <= t and they have the same length. If s[0..d-1] > t[0..d-1], then any extension // of s[0..d-1] > any extension of t[0..d-1], so s > t, contradiction. // // Oh wait, that's not quite right because we're comparing the full strings. Let me think. // s = s[0..n-1] <= t = t[0..n-1] lexicographically. Does this imply s[0..d-1] <= t[0..d-1]? // Not necessarily for all d! For example, s = "ab" and t = "ba". s < t (comparing first char 'a' < 'b'). // s[0..1] = "ab", t[0..1] = "ba". As binary numbers: "ab" = 01, "ba" = 10. So val(s) = 1, val(t) = 2. // s[0..0] = "a" = 0, t[0..0] = "b" = 1. OK both are fine. // But consider s = "ba", t = "bb". s < t. // s[0..0] = "b" = 1, t[0..0] = "b" = 1. c_1 = 1. Fine. // s[0..1] = "ba" = 10, t[0..1] = "bb" = 11. c_2 = 2. Fine. // Another: s = "aba", t = "bab". s < t. // d=1: s[0]='a'=0, t[0]='b'=1. diff=1. c=2. // d=2: diff = 2*1 + (0-1) = 1. c=2. // s[0..1] = "ab" = 01, t[0..1] = "ba" = 10. diff = 10 - 01 = 1. c=2. ✓ // d=3: diff = 2*1 + (1-0) = 3. c=4. // s[0..2] = "aba" = 010, t[0..2] = "bab" = 101. diff = 5 - 2 = 3. c=4. ✓ // So diff is always >= 0 (since s <= t implies val(s[0..d-1]) <= val(t[0..d-1]) for all d). // Proof: if s <= t (lex), then for the first position i where they differ, s[i] < t[i]. // For d <= i: s[0..d-1] = t[0..d-1], diff = 0. // For d = i+1: diff = 2*0 + (t[i] - s[i]) > 0. // For d > i+1: diff = 2*prev_diff + (t[d-1] - s[d-1]) >= 2*prev_diff - 1. // Since prev_diff >= 1 (after d = i+1), 2*prev_diff - 1 >= 1. So diff >= 1. // By induction, diff >= 0 always. // Great. So diff is always non-negative after d > lcp, and it grows roughly exponentially. // Once diff + 1 >= k, i.e., diff >= k - 1: // For all subsequent d': diff_{d'} >= 2 * (k-1) - 1 >= k - 1 (for k >= 1). // Actually, diff_{d'} = 2 * diff_d + delta >= 2*(k-1) - 1 = 2k - 3. // For k >= 2: 2k - 3 >= k - 1. So yes, once diff >= k-1, it stays >= k-1. // For k = 1: diff >= 0 always, and c_d >= 1 always, so min(1, c_d) = 1 always. Answer = n. // Perfect. So the algorithm is O(n) in the worst case but actually O(lcp + log k) for the // computation after lcp, which is fast. // Wait, but after the break (when diff >= k-1), we add k * (n - d) for the remaining depths. // And before that, we iterate at most about 30 times. So total is O(n) for computing lcp + O(log k) for the rest. // Actually computing lcp is O(n) in the worst case. That's fine since n <= 5*10^5. // Edge case: k = 1. Answer = n (pick any single string, it has n prefixes of lengths 1..n). // But wait, do all lengths 1..n give distinct prefixes? A single string of length n has exactly n // distinct prefixes (lengths 1 through n), so yes, answer = n. // But wait, is that consistent with our formula? For k=1, min(1, c_d) = 1 for all d, sum = n. ✓ // Another edge case: when the total available strings in [s,t] are fewer than k. // Total available = val(t) - val(s) + 1 = diff_n + 1 = c_n. // If c_n < k, we can only pick c_n strings. So effective k = min(k, c_n). // But in our formula, at depth n, min(k, c_n). If c_n < k, then at depth n, contribution is c_n. // And at earlier depths, c_d <= c_n < k, so all min(k, c_d) = c_d. // Hmm wait, c_d is non-decreasing? c_{d+1} = val(t[0..d]) - val(s[0..d]) + 1. // c_{d+1} = 2*diff_d + (t[d] - s[d]) + 1. // = 2*(c_d - 1) + (t[d] - s[d]) + 1 // = 2*c_d - 2 + (t[d] - s[d]) + 1 // = 2*c_d - 1 + (t[d] - s[d]). // Since t[d] - s[d] >= -1: c_{d+1} >= 2*c_d - 2. // For c_d >= 2: c_{d+1} >= 2. And c_{d+1} <= 2*c_d + 1 (when t[d]=1, s[d]=0). // Is c_d always non-decreasing? c_{d+1} >= 2*c_d - 2. If c_d >= 2, c_{d+1} >= 2. // Is c_{d+1} >= c_d? c_{d+1} = 2*c_d - 1 + (t[d]-s[d]) >= 2*c_d - 2. // If c_d >= 2: 2*c_d - 2 >= c_d iff c_d >= 2. Yes. // If c_d = 1: c_{d+1} = 2*1 - 1 + (t[d]-s[d]) = 1 + (t[d]-s[d]). // Since d <= lcp implies c_d = 1. At d = lcp: c_{lcp} = 1. // c_{lcp+1} = 1 + (t[lcp]-s[lcp]) = 1 + (1-0) = 2. OK, still non-decreasing. // So c_d is non-decreasing. // Good. So if k > c_n, we just use c_d for all depths (no capping needed). // But we might not know c_n without computing diff for all n depths. However, if diff never // reaches k-1 by depth n, we just sum all c_d = diff_d + 1. // But computing diff for all depths from lcp+1 to n takes O(n - lcp) time. // Since n can be 5*10^5, this is fine. // Wait, but diff can grow exponentially! After about 40 steps, diff exceeds 10^12. // After 60+ steps, it overflows int64. We need to be careful. // Solution: once diff >= k, we can cap it. We don't need the exact value; we just need to know // if diff + 1 >= k. So we can cap diff at k (or some large value like 2*10^9) to prevent overflow. // Here's the refined algorithm: // answer = lcp // diff = 0 // capped = false // for d = lcp+1 to n: // td = (t[d-1] == 'b') ? 1 : 0 // sd = (s[d-1] == 'b') ? 1 : 0 // diff = 2*diff + (td - sd) // if diff + 1 >= k: // answer += k * (n - d + 1) // k for depth d through n // capped = true // break // else: // answer += diff + 1 // Wait, I need to be careful. Once diff >= k-1, all remaining depths give k each. // remaining depths = d, d+1, ..., n. Count = n - d + 1. // answer += k * (n - d + 1). // Then break. // But diff = 2*prev + delta can overflow. We need to detect overflow. // Since k <= 10^9, once diff >= 10^9, it stays >= 10^9 (as we showed, it at least doubles minus 1). // So we can cap diff at, say, 2 * 10^9 to prevent overflow. // Actually let me be more careful. diff fits in int64 for a while. // diff starts at 0. Each step: diff = 2*diff + delta where delta in {-1, 0, 1}. // After about 62 steps from lcp, diff could overflow int64. But k <= 10^9, and diff >= k-1 happens // within about 30 steps. So I'll cap diff at k (once diff >= k, set diff = k, since 2*k + 1 won't // overflow int64 and diff will remain >= k forever). // Hmm, but once diff >= k, future diff = 2*diff + delta >= 2k - 1 >= k for k >= 1. So capping at k is fine. But actually 2*diff might already overflow before we detect it's >= k if we're not careful. Let me cap more conservatively: if diff > 2*10^18, cap it. Actually, within 62 iterations, it can reach 2^62, which overflows int64. But we only need about 31 iterations before it exceeds 10^9. So let's cap at 2*10^9 to be safe. // Let me implement this properly. answer := int64(lcp) diff := int64(0) found := false bigK := int64(k) for d := lcp + 1; d <= n; d++ { td := int64(0) if t[d-1] == 'b' { td = 1 } sd := int64(0) if s[d-1] == 'b' { sd = 1 } diff = 2*diff + (td - sd) if diff+1 >= bigK { answer += bigK * int64(n-d+1) found = true break } answer += diff + 1 } _ = found fmt.Println(answer) } ``` Hmm wait, let me reconsider. Let me re-examine my key claim more carefully. The claim is: Answer = sum_{d=1}^{n} min(k, c_d), where c_d = number of strings of length d that are prefixes of at least one string in [s,t]. And I showed c_d = val(t[0..d-1]) - val(s[0..d-1]) + 1. Let me double-check with example 3 mentioned in the problem notes: "In the third example, there are only two different strings that Nut could write. If both of them are written, c=8." I don't have the exact input for example 3, but it says n=some value, k=2, and there are exactly 2 available strings. The answer is 8. Hmm, I can't verify without the exact input. Let me trust my derivation and verify correctness of the code logic. Actually wait - I just realized there may be an issue with my proof that the answer is sum min(k, c_d). Let me reconsider. The claim is that for any k, we can find a set of k leaves (from the available set) that simultaneously achieves min(k, c_d) distinct prefixes at every depth d. Consider depth d where c_d = 3, and depth d+1 where c_{d+1} = 4. If k = 4, then at depth d we want 3 (since c_d = 3), and at depth d+1 we want 4. At depth d, the 3 nodes each have some descendants at depth d+1. One of them has 2 descendant depth-(d+1) nodes (since c_{d+1} = 4 and 4 - 2 = 2 of the remaining 3... hmm this is complex). Actually, since c_d is non-decreasing and the tree is binary, each node at depth d has either 1 or 2 children at depth d+1 with available leaves. The sum equals c_{d+1}. We want to pick k = 4 leaves such that at depth d, all 3 nodes are covered, and at depth d+1, all 4 nodes are covered. Since c_{d+1} = 4, there are 4 depth-(d+1) nodes with leaves. We can pick one leaf from each of these 4 nodes. At depth d, the 4 chosen leaves cover how many depth-d nodes? Each depth-(d+1) node is a child of a depth-d node. The 4 depth-(d+1) nodes are children of the 3 depth-d nodes. So the 4 leaves cover all 3 depth-d nodes. ✓ In general: pick min(k, c_n) leaves, one from each of min(k, c_n) distinct depth-n nodes (i.e., distinct leaves). At each depth d, these leaves cover min(k, c_d) distinct depth-d nodes? Not necessarily! Counter-example attempt: Depth d: 2 nodes, A and B. A has 1 child at d+1, B has 2 children at d+1. c_d = 2, c_{d+1} = 3. k = 3. We pick one leaf from each of 3 depth-(d+1) nodes. At depth d: A's child has 1 leaf, B's children have 2 leaves. All 3 leaves cover both A and B. min(3, 2) = 2. ✓ Another: depth d has 2 nodes. c_{d+1} = 3 (one has 1 child, other has 2). c_{d+2}: each child at d+1 has 2 children at d+2 (for a total of 6), but only 5 have available leaves. k = 3. We pick 3 leaves from 5 available depth-(d+2) nodes. At depth d+1, they cover at least... hmm, it depends on which 3 we pick. If we pick 3 from the 2 children of B's children, we might miss A's subtree. So we need to pick carefully! The question is: CAN we always find a selection achieving min(k, c_d) at all depths? Let me think about this more carefully with a potential counter-example. Consider n=3: ``` root / \ 0 1 / \ / \ 00 01 10 11 /\ /\ /\ /\ ... ``` Suppose s = "aab" and t = "bba". Available strings: aab, aba, abb, baa, bab, bba. (6 strings) k = 3. c_1: "a" and "b" both have available strings. c_1 = 2. c_2: "aa" (has aab ✓), "ab" (has aba, abb ✓), "ba" (has baa, bab ✓), "bb" (has bba ✓). c_2 = 4. c_3: 6. min(3, 2) + min(3, 4) + min(3, 6) = 2 + 3 + 3 = 8. Can we achieve this? We need 3 leaves covering 2 depth-1 nodes, 3 depth-2 nodes, and 3 depth-3 nodes. Pick: aab, baa, bba. Depth 1: a, b → 2 ✓ Depth 2: aa, ba, bb → 3 ✓ Depth 3: aab, baa, bba → 3 ✓ Total: 8 ✓ Now, can there be a case where it fails? I believe the answer is always sum min(k, c_d) and here's a cleaner proof: Proof: We prove by induction that we can always achieve min(k, c_d) at every depth simultaneously. For a tree rooted at some node, with c_d being the number of depth-d nodes with available leaves. We select m = min(k, c_n) leaves (one per distinct leaf node if possible). Claim: if we greedily select leaves to spread across as many depth-d nodes as possible (for each d), we achieve the optimum. Actually, here's a simpler proof: - Consider the bipartite graph between depth-d nodes and depth-(d+1) nodes (edges connect parent-child). - At each depth, we want to cover min(k, c_d) nodes. - Since c_d is non-decreasing, min(k, c_d) is non-decreasing. - At each depth, a "covered" node at depth d must have at least one "covered" child at depth d+1. - So min(k, c_{d+1}) >= min(k, c_d) (since we need at least that many depth-(d+1) nodes to cover min(k, c_d) depth-d nodes). - This is consistent. For the actual construction: pick any min(k, c_n) distinct available leaf nodes. For each leaf, trace its path to the root. The set of activated depth-d nodes is exactly the set of depth-d ancestors of the selected leaves. The number of distinct depth-d ancestors of min(k, c_n) leaves: is this always min(k, c_d)? Each depth-d node has at most 2^(n-d) descendants. If we pick min(k, c_n) leaves and try to spread them, at depth d we can cover at most c_d nodes (since only c_d have available leaves) and at most min(k, c_n) >= min(k, c_d) (since c_n >= c_d). But can we always achieve min(k, c_d)? I think the key insight is: if we pick leaves greedily (at each internal node, try to put leaves in both subtrees if possible), we achieve the maximum spread at every level. Formally: given a subtree with root v, available leaves = A(v), and we allocate m strings (m <= A(v)): - if v is a leaf: m = 1 (or 0), contribution = m. - if v has children u, w with available leaves A(u), A(w): - m_u = min(A(u), max(1, m - A(w))) ... actually let's say: - m_u = min(A(u), m), m_w = m - m_u... no this doesn't work simply. OK I think the claim holds but proving it rigorously is complex. Let me just verify with a few more examples and trust the approach. Let me verify with example 3 from the problem. The note says "there are only two different strings that Nut could write. If both are written, c=8." So n is some value, k is some value (at least 2), and with 2 strings, c=8. This means n >= 4 (since 2 strings give at most 2*n activated nodes minus shared prefix). With n=5, 2 strings diverging at depth 2 give: 2 + 2*3 = 8 prefix nodes. So n=5, and the two strings share a prefix of length 2 and diverge after that. Answer would be: d=1: min(k, 1) = 1 (shared prefix) d=2: min(k, 1) = 1 d=3: min(k, 2) = 2 d=4: min(k, 2) = 2 d=5: min(k, 2) = 2 Total: 1+1+2+2+2 = 8. ✓ Great, my formula works. Let me clean up the code. ```go package main import ( "bufio" "fmt" "os" ) func main() { reader := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(reader, &n, &k) var s, t string fmt.Fscan(reader, &s) fmt.Fscan(reader, &t) // answer = sum_{d=1}^{n} min(k, c_d) // where c_d = val(t[0..d-1]) - val(s[0..d-1]) + 1 // c_d can be computed incrementally: diff_d = 2*diff_{d-1} + (t[d-1] - s[d-1]) // c_d = diff_d + 1 // For d <= lcp: c_d = 1, contribute 1 each. // For d > lcp: compute diff incrementally, cap when diff+1 >= k. lcp := 0 for lcp < n && s[lcp] == t[lcp] { lcp++ } answer := int64(lcp) diff := int64(0) bigK := int64(k) for d := lcp + 1; d <= n; d++ { td := int64(0) if t[d-1] == 'b' { td = 1 } sd := int64(0) if s[d-1] == 'b' { sd = 1 } diff = 2*diff + (td - sd) // Cap diff to prevent overflow if diff+1 >= bigK { answer += bigK * int64(n-d+1) break } answer += diff + 1 } fmt.Println(answer) } ``` Wait, I need to handle the case where diff might overflow before we detect it's >= k. Let me add a cap. Actually, diff starts at 0. After the first iteration (d = lcp+1), diff = 1 (since t[lcp]='b', s[lcp]='a'). Then each subsequent step: diff = 2*diff + delta where delta ∈ {-1, 0, 1}. Maximum growth: diff roughly doubles. After 62 iterations, diff could be around 2^62, which overflows int64. But we check diff+1 >= bigK each iteration, and bigK <= 10^9, so after about 31 iterations, diff >= 10^9 and we break. So in practice, diff won't overflow. But to be safe, I should cap diff at bigK when it exceeds bigK: ```go diff = 2*diff + (td - sd) if diff >= bigK { diff = bigK // cap to prevent overflow in next iteration } ``` Actually, once diff >= bigK, diff+1 > bigK, so the condition diff+1 >= bigK triggers and we break. So the cap isn't needed as long as 2*diff doesn't overflow before the check. Since diff < bigK before the update, after update diff < 2*bigK + 1 <= 2*10^9 + 1, which fits in int64. So no overflow possible. Let me finalize: ```go package main import ( "bufio" "fmt" "os" ) func main() { reader := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(reader, &n, &k) var s, t string fmt.Fscan(reader, &s) fmt.Fscan(reader, &t) lcp := 0 for lcp < n && s[lcp] == t[lcp] { lcp++ } answer := int64(lcp) diff := int64(0) bigK := int64(k) for d := lcp + 1; d <= n; d++ { var td, sd int64 if t[d-1] == 'b' { td = 1 } if s[d-1] == 'b' { sd = 1 } diff = 2*diff + (td - sd) if diff+1 >= bigK { answer += bigK * int64(n-d+1) break } answer += diff + 1 } fmt.Println(answer) } ``` Let me trace through the examples: Example 1: n=2, k=4, s="aa", t="bb" lcp = 0 (s[0]='a' != t[0]='b') answer = 0 d=1: td=1, sd=0, diff = 0 + 1 = 1. diff+1=2 < 4. answer += 2 → answer=2. d=2: td=1, sd=0, diff = 2+1 = 3. diff+1=4 >= 4. answer += 4*(2-2+1) = 4. answer=6. Output: 6 ✓ Example 2: n=3, k=3, s="aba", t="bba" lcp = 0 (s[0]='a' != t[0]='b') answer = 0 d=1: td=1, sd=0, diff=1. diff+1=2 < 3. answer += 2 → answer=2. d=2: td=1, sd=1, diff=2+0=2. diff+1=3 >= 3. answer += 3*(3-2+1) = 6. answer=8. Output: 8 ✓ Looks correct! Let me also check: what if s = t? lcp = n, answer = n. The loop doesn't execute. Output: n. For k >= 1, picking the single string gives n prefixes. ✓ What if k = 1? Then bigK = 1. At d = lcp+1: diff = 1, diff+1 = 2 >= 1. answer += 1*(n-lcp). answer = lcp + (n-lcp) = n. ✓ What about s = "ab", t = "ba", n=2, k=3? Available strings: ab, ba, bb. Wait, is that right? Strings from "ab" to "ba" of length 2: ab, ba. That's 2 strings. k=3 but only 2 available. lcp = 0. d=1: td=1, sd=0, diff=1. diff+1=2 < 3. answer += 2. d=2: td=0, sd=1, diff=2-1=1. diff+1=2 < 3. answer += 2. Total: 4. Hmm, with 2 strings "ab" and "ba", picking both: Prefixes: a, b (length 1), ab, ba (length 2) = 4. ✓ But k=3, we can only pick 2. Answer is still 4. And our formula gives 4. ✓ (We don't need to worry about k > available; the formula naturally handles it because c_d <= c_n = total available, and if k > c_n, then min(k, c_d) = c_d for all d.) Great, the solution is correct. Let me write the final version. ```go package main import ( "bufio" "fmt" "os" ) func main() { reader := bufio.NewReader(os.Stdin) var n, k int fmt.Fscan(reader, &n, &k) var s, t string fmt.Fscan(reader, &s) fmt.Fscan(reader, &t) lcp := 0 for lcp < n && s[lcp] == t[lcp] { lcp++ } answer := int64(lcp) diff := int64(0) bigK := int64(k) for d := lcp + 1; d <= n; d++ { var td, sd int64 if t[d-1] == 'b' { td = 1 } if s[d-1] == 'b' { sd = 1 } diff = 2*diff + (td - sd) if diff+1 >= bigK { answer += bigK * int64(n-d+1) break } answer += diff + 1 } fmt.Println(answer) } ```