Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

شنگدباو در فراق یار و نبود کار حوصله‌اش سر رفته‌ بود و تصمیم به حل سوالی گرفت. صورت سوال…

  1. User

    شنگدباو در فراق یار و نبود کار حوصله‌اش سر رفته‌ بود و تصمیم به حل سوالی گرفت. صورت سوال طولانی بود. به قول یکی از دوستان شنگدباو «همیشه که نباید سوالا رو پیچوند! بعضی وقتا باید ساده حرف زد!» در نتیجه تصمیم گرفت حالت ساده شده‌ی صورت سوال را قرار دهد:

    تعداد n n رشته داده شده است، رشته‌ی i iام s i s i ​ می‌باشد. به ازای هر رشته لیستی از اعداد موجود است، لیست متناظر با رشته‌ی i iام شامل ∣ s i ∣ + 1 ∣s i ​ ∣+1 عدد است که عدد j jام آن (با شروع از صفر)‌ مقدار a i , j a i,j ​ دارد. ( 1 ≤ i ≤ n 1≤i≤n ، 0 ≤ j ≤ ∣ s i ∣ 0≤j≤∣s i ​ ∣)

    هزینه‌ی رفتن از رشته‌ی s i s i ​ به s j s j ​ برابر است با a j , l c p ( s i , s j ) a j,lcp(s i ​ ,s j ​ ) ​ (منظور از l c p ( s , p ) lcp(s,p) طول بزرگترین پیشوند مشترک دو رشته‌ی s s و p p است)

    فرض کنید روی رشته‌ی s A s A ​ قرار داریم و می‌خواهیم به رشته‌ی s B s B ​ برسیم. کمینه هزینه برای انجام این‌ کار را باید خروجی دهید.»

    شنگدباو سوال را حل کرده است! آیا شما هم می‌توانید آن‌ را حل کنید؟

    ورودی در سطر اول ورودی عدد n n داده شده است. سپس در 2 × n 2×n سطر بعدی ابتدا رشته‌ی ناتهی i i ام آمده است و سپس لیست متناظر با رشته‌ی مورد نظر آمده‌ است. در سطر آخر نیز ۲ عدد آمده است که اولی A A و دومی B B است.

    1 ≤ n ≤ 500

    000 1≤n≤500 000 0 ≤ a i , j ≤ 1 0 9 0≤a i,j ​ ≤10 9

    ∑ ∣ s i ∣ ≤ 500

    000 ∑∣s i ​ ∣≤500 000 A ≠ B A  =B

    رشته های ورودی از حروف کوچک الفبا تشکیل شده‌اند. خروجی در تنها سطر خروجی کمترین هزینه برای رفتن از s A s A ​ به s B s B ​ را خروجی دهید.

    زیر مسئله‌ها زیرمسئله نمره محدودیت ۱ ۲۰ n ≤ 5

    000 n≤5 000 ۲ ۲۰ به ازای هر 0 ≤ j < a b s ( s i ) 0≤j<abs(s i ​ ) داریم: a i , j + 1 − a i , j

    1 a i,j+1 ​ −a i,j ​ =1 ۳ ۲۰ رشته‌ها فقط از حروف a a و b b تشکیل شده اند. ۴ ۴۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 3 a 0 1 b 0 1 a 0 1 1 3 Plain text خروجی نمونه ۱ 0 Plain text ورودی نمونه ۲ 3 abcd 0 1 2 3 4 abc 0 1 2 3 abcde 0 1 2 10 1 2 2 3 Plain text خروجی نمونه ۲ 4 Plain text ورودی نمونه ۳ 4 shengdebao 10 11 12 13 14 15 16 17 18 19 20 bao 4 3 2 7 barricade 1 13 12 11 10 9 8 7 6 5 baran 7 14 3 14 7 6 1 4 Plain text خروجی نمونه ۳ 6 java

  2. Assistant

    The problem is to find the minimum cost to reach from string s_A to s_B, where the cost from s_i to s_j is a_j, lcp(s_i,s_j), with lcp(s_i,s_j) being the length of the longest common prefix of s_i and s_j.

    Given the large constraints, we can't consider all possible pairs of strings. Instead, we can model the problem using Dijkstra's algorithm on a trie (prefix tree) of all the strings.

    Here's how you can solve the problem:

    1. Build a Trie:

      • Construct a trie from all input strings. Each node represents a prefix.
    2. Initialize Distances:

      • For each node (prefix) in the trie, initialize the distance dist[p] to infinity (INF), except for the starting string s_A, where dist[s_A] = 0.
    3. Dijkstra's Algorithm:

      • Use a priority queue to perform Dijkstra's algorithm.
      • At each step, pop a node p with the smallest dist[p] from the queue.
      • For each neighbor p' of p (which can be the parent or children in the trie), if dist[p'] > dist[p], update dist[p'] = dist[p] and push p' onto the queue.
      • Important: If p corresponds to a complete string s_i (i.e., it's a leaf node), add the cost a_i, |p| to dist[p] if it hasn't been added before.
    4. Track Visited Strings:

      • Maintain a set to keep track of strings (leaf nodes) for which you've already added the cost to avoid adding the cost multiple times.
    5. Termination:

      • Continue the algorithm until the priority queue is empty or until you reach s_B.
      • The minimum cost to reach s_B will be dist[s_B].
    6. Output:

      • Print the minimum cost to reach from s_A to s_B.

    Here's the code that implements the above approach:

    from collections import defaultdict
    import sys
    import threading
    import heapq
    
    def main():
        import sys
        sys.setrecursionlimit(1 << 25)
        input = sys.stdin.readline
        n = int(sys.stdin.readline())
        trie = {}
        end_nodes = {}
        a_values = {}
    
        class Node:
            def __init__(self):
                self.children = {}
                self.parent = None
                self.char = ''
                self.is_end = False
                self.a_i = []
                self.dist = float('inf')
    
        root = Node()
    
        strings = []
        for _ in range(n):
            s = sys.stdin.readline().strip()
            s_node = root
            for c in s:
                if c not in s_node.children:
                    child = Node()
                    child.parent = s_node
                    child.char = c
                    s_node.children[c] = child
                s_node = s_node.children[c]
            s_node.is_end = True
            strings.append(s_node)
    
            a_i = list(map(int, sys.stdin.readline().strip().split()))
            a_values[s_node] = a_i
    
        A_str, B_str = map(int, sys.stdin.readline().strip().split())
        s_A = strings[A_str -1]
        s_B = strings[B_str -1]
    
        visited_strings = set()
    
        import heapq
        hq = []
        s_A.dist = 0
        heapq.heappush(hq, (s_A.dist, s_A))
    
        while hq:
            dist_u, u = heapq.heappop(hq)
            if u.dist < dist_u:
                continue
            if u == s_B and u.is_end:
                print(int(u.dist))
                return
            if u.is_end and u not in visited_strings:
                # Add cost a_i,|u|
                a_i = a_values[u]
                u.dist += a_i[len(a_i)-1]
                visited_strings.add(u)
            for v in u.children.values():
                if v.dist > u.dist:
                    v.dist = u.dist
                    heapq.heappush(hq, (v.dist, v))
            if u.parent:
                v = u.parent
                if v.dist > u.dist:
                    v.dist = u.dist
                    heapq.heappush(hq, (v.dist, v))
    
        # If s_B is not reachable
        print(int(s_B.dist))
    
    threading.Thread(target=main).start()
    

    This code handles the problem within the constraints and efficiently calculates the minimum cost without considering all possible pairs of strings.