{"id":2307,"date":"2017-03-10T11:10:20","date_gmt":"2017-03-10T07:40:20","guid":{"rendered":"https:\/\/blog.quera.ir\/?p=1369"},"modified":"2017-03-10T11:10:20","modified_gmt":"2017-03-10T07:40:20","slug":"editorial17","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/editorial17\/","title":{"rendered":"\u0631\u0627\u0647 \u062d\u0644 \u0647\u0627\u06cc \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 \u06f1\u06f7 Quera"},"content":{"rendered":"

\u06cc\u0647 \u06a9\u0645 \u062f\u06cc\u0631 \u0634\u062f \u0648\u0644\u06cc \u0627\u0645\u06cc\u062f \u0648\u0627\u0631\u0645 \u0627\u0632 \u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627 \u0644\u0630\u062a \u0628\u0628\u0631\u06cc\u062f (\u0645\u062b \u0633\u0648\u0627\u0644\u0627 \u06a9\u0647 \u0644\u0630\u062a \u0628\u0631\u062f\u06cc\u062f ?).<\/p>\n

\u0631\u0627\u0647 \u062d\u0644 \u0647\u0627 \u062f\u0631 \u0627\u062f\u0627\u0645\u0647\u200c\u06cc \u0645\u0637\u0644\u0628 \u0645\u0648\u062c\u0648\u062f \u0627\u0633\u062a. \u0647\u0645\u200c\u0686\u0646\u06cc\u0646 \u0628\u0631\u0627\u06cc \u0647\u0645\u0647\u200c\u06cc \u0633\u0648\u0627\u0644\u200c\u0647\u0627 \u062c\u0632 \u0633\u0648\u0627\u0644 \u0622\u062e\u0631\u060c \u06a9\u062f \u0627\u0648\u0644\u06cc\u0646 \u06a9\u0633\u06cc \u06a9\u0647\u00a0\u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u0631\u0627 \u062d\u0644 \u06a9\u0631\u062f\u0647 \u0642\u0627\u0628\u0644 \u0645\u0634\u0627\u0647\u062f\u0647 \u0627\u0633\u062a.<\/p>\n

\u0646\u0627\u0645\u0647\u200c\u06cc \u0628\u062f<\/b><\/a><\/p>\n

\u0637\u0648\u0644 \u0647\u0631 \u06a9\u0644\u0645\u0647 \u0631\u0648 \u062d\u0633\u0627\u0628 \u06a9\u0646\u06cc\u062f \u0628\u0628\u06cc\u0646\u06cc\u062f \u0622\u06cc\u0627 \u0647\u0645\u0647 \u0632\u0648\u062c \u0647\u0633\u062a\u0646 \u06cc\u0627 \u0646\u0647.\u00a0O(n^2)<\/span> \u06cc\u0627\u00a0O(n)<\/span><\/p>\n

\u06cc\u0627<\/p>\n

\u0686\u06a9 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0647\u0631 \u062d\u0631\u0641\u06cc \u06a9\u0647 \u062f\u0631 \u062c\u0627\u06cc\u06af\u0627\u0647 \u0632\u0648\u062c (\u062f\u0648\u0645\u06cc\u0646 \u062d\u0631\u0641\u060c \u0686\u0647\u0627\u0631\u0645\u06cc\u0646 \u062d\u0631\u0641\u060c \u0634\u0634\u0645\u06cc\u0646 \u062d\u0631\u0641\u060c …) \u0622\u0645\u062f\u0647\u200c\u0627\u0646\u062f \u0628\u0627 \u062d\u0631\u0641 \u0642\u0628\u0644\u06cc \u0628\u0631\u0627\u0628\u0631 \u0628\u0627\u0634\u0646\u062f.\u00a0O(n)<\/span><\/p>\n

\u06a9\u062f ++c \u0627\u0632 \u0645\u0647\u062f\u06cc \u062c\u0639\u0641\u0631\u06cc\u060c \u0631\u0627\u0647 \u062d\u0644 \u0627\u0648\u0644 \u06af\u0641\u062a\u0647 \u0634\u062f\u0647.<\/a><\/p>\n

\u062c\u0641\u0627\u06cc \u06cc\u0627\u0631<\/strong><\/a><\/p>\n

\u062f\u0642\u06cc\u0642\u0646 \u0645\u062b\u0644 \u062f\u0633\u062a\u0648\u0631 \u06a9\u0627\u0631 \u062f\u0633\u062a\u06af\u0627\u0647 \u0639\u0645\u0644 \u06a9\u0646\u06cc\u062f\u061b \u0631\u0648\u0646\u062f \u0627\u0639\u0645\u0627\u0644 \u062f\u0633\u062a\u06af\u0627\u0647 \u0631\u0627 \u0628\u0627 \u062f\u0642\u062a \u067e\u06cc\u0627\u062f\u0647\u200c\u0633\u0627\u0632\u06cc \u06a9\u0646\u06cc\u062f.<\/p>\n

\u0628\u0631\u0627\u06cc \u067e\u06cc\u0627\u062f\u0647\u200c\u0633\u0627\u0632\u06cc \u0633\u0627\u062f\u0647\u200c\u062a\u0631:<\/p>\n

\u0628\u0631\u0627\u06cc \u0647\u0631 \u0648\u0636\u0639\u06cc\u062a \u0642\u0627\u0646\u0648\u0646\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0648\u0636\u0639\u06cc\u062a \u0627\u0628\u062a\u062f\u0627\u06cc\u06cc \u0622\u0646\u200c\u0647\u0627 \u0622\u0646 \u0648\u0636\u0639\u06cc\u062a \u0627\u0633\u062a \u0631\u0627 \u0646\u06af\u0647 \u062f\u0627\u0631\u06cc\u062f \u0648 \u0633\u067e\u0633 \u0645\u062b\u0644 \u062f\u0633\u062a\u0648\u0631 \u06a9\u0627\u0631 \u062f\u0633\u062a\u06af\u0627\u0647 \u0639\u0645\u0644 \u06a9\u0646\u06cc\u062f.<\/p>\n

\u06a9\u062f ++C \u0627\u0632 \u0627\u0645\u06cc\u062f \u0622\u0632\u0627\u062f\u06cc<\/a><\/p>\n

\u0641\u0631\u0627\u0631 \u06cc\u0627\u0631<\/strong><\/a><\/p>\n

\u0628\u0631\u0627\u06cc \u0647\u0631 \u0627\u062a\u0627\u0642 \u0645\u062f\u062a \u0632\u0645\u0627\u0646\u06cc \u06a9\u0647 \u0637\u0648\u0644 \u0645\u06cc\u200c\u06a9\u0634\u062f \u062a\u0627 \u0628\u0639\u062f \u0627\u0632 \u0627\u06cc\u0646 \u06a9\u0647 \u0627\u0632 \u0627\u062a\u0627\u0642 \u0642\u0628\u0644\u06cc \u0648\u0627\u0631\u062f \u0622\u0646 \u0627\u062a\u0627\u0642 \u0634\u062f\u06cc\u0645 \u0627\u0632 \u062f\u0631 \u062e\u0631\u0648\u062c\u06cc \u0627\u062a\u0627\u0642 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u0645 \u0639\u062f\u062f\u06cc \u062b\u0627\u0628\u062a \u0627\u0633\u062a \u0648 \u0628\u0627 \u062f\u0627\u0634\u062a\u0646 \u0639\u062f\u062f\u00a0\u0631\u0648\u06cc \u062f\u0631 \u062e\u0631\u0648\u062c\u06cc \u0622\u0646\u200c\u0647\u0627 \u0648 \u0645\u0642\u062f\u0627\u0631 k<\/span> \u0642\u0627\u0628\u0644 \u0645\u062d\u0627\u0633\u0628\u0647 \u0627\u0633\u062a. \u0648 \u062c\u0648\u0627\u0628 \u0647\u0631 \u0627\u062a\u0627\u0642 \u0628\u0631\u0627\u0628\u0631 \u0645\u062c\u0645\u0648\u0639\u00a0\u062c\u0648\u0627\u0628 \u0627\u062a\u0627\u0642 \u0628\u0639\u062f\u06cc \u0648 \u0645\u0642\u062f\u0627\u0631 \u0632\u0645\u0627\u0646\u06cc\u0633\u062a \u06a9\u0647 \u0637\u0648\u0644 \u0645\u06cc\u200c\u06a9\u0634\u062f \u062a\u0627 \u0627\u0632 \u0627\u06cc\u0646 \u0627\u062a\u0627\u0642 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u0645.<\/p>\n

\u06a9\u062f ++C \u0627\u0632 \u0645\u062d\u0645\u062f \u0646\u0639\u0645\u062a\u200c\u0627\u0644\u0644\u0647\u06cc<\/a><\/p>\n

\u06cc\u0627\u0631 \u0648 \u0686\u0631\u062e\u200c\u062f\u0646\u062f\u0647\u200c\u0647\u0627<\/strong><\/a><\/p>\n

\u0645\u0633\u0626\u0644\u0647 \u0631\u0627 \u0628\u0627 \u06af\u0631\u0627\u0641 \u0645\u062f\u0644 \u06a9\u0646\u06cc\u062f. \u0627\u06af\u0631 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631 \u0686\u0631\u062e\u200c\u062f\u0646\u062f\u0647\u200c\u0627\u06cc \u062f\u0631 \u06cc\u06a9 \u0645\u0648\u0644\u0647 \u0647\u0645\u0628\u0646\u062f\u06cc \u063a\u06cc\u0631 \u062f\u0648 \u0628\u062e\u0634\u06cc \u0628\u0627\u0634\u062f\u060c \u0622\u0646 \u0686\u0631\u062e\u200c\u062f\u0646\u062f\u0647 \u0647\u06cc\u0686 \u0648\u0642\u062a \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u0628\u0686\u0631\u062e\u062f. \u0627\u06af\u0631 \u062f\u0648 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631 \u062f\u0648 \u0686\u0631\u062e\u200c\u062f\u0646\u062f\u0647 \u062f\u0631 \u062f\u0648 \u0645\u0648\u0644\u0641\u0647\u200c\u06cc \u0645\u062e\u062a\u0644\u0641 \u0628\u0627\u0634\u0646\u062f \u0686\u0631\u062e\u06cc\u062f\u0646 \u06cc\u06a9\u06cc \u0627\u0632 \u0622\u0646\u200c\u0647\u0627\u060c \u0628\u0631 \u062f\u06cc\u06af\u0631\u06cc \u0627\u062b\u0631\u06cc \u0646\u0645\u06cc\u200c\u06af\u0630\u0627\u0631\u062f. \u0627\u06af\u0631 \u0647\u0631 \u062f\u0648 \u062f\u0631 \u0645\u0648\u0644\u0641\u0647\u200c\u0627\u06cc \u062f\u0648 \u0628\u062e\u0634\u06cc \u0628\u0627\u0634\u0646\u062f \u0628\u0627\u00a0\u200c\u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u06cc\u0646 \u06a9\u0647 \u062f\u0631 \u06cc\u06a9 \u0628\u062e\u0634 \u0642\u0631\u0627\u0631 \u062f\u0627\u0631\u0646\u062f \u06cc\u0627 \u0646\u0647 \u062c\u0647\u062a \u062d\u0631\u06a9\u062a \u0622\u0646\u200c\u0647\u0627 \u0646\u0633\u0628\u062a \u0628\u0647 \u0647\u0645 \u0645\u0634\u062e\u0635 \u0645\u06cc\u200c\u0634\u0648\u062f. \u067e\u0633 \u0645\u0627 \u06cc\u06a9 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0645\u0648\u0644\u0641\u0647\u200c\u0647\u0627 \u0648 \u062f\u0648\u0628\u062e\u0634\u06cc \u0628\u0648\u062f\u0646 \u06cc\u0627 \u0646\u0628\u0648\u062f\u0646 \u0622\u0646\u200c\u0647\u0627 \u0631\u0627 \u0645\u0634\u062e\u0636 \u06a9\u0646\u06cc\u0645 \u0648 \u0645\u0633\u0626\u0644\u0647 \u062d\u0644 \u0645\u06cc\u200c\u0634\u0648\u062f.<\/p>\n

\u06a9\u062f ++C \u0627\u0632 \u0645\u062d\u0645\u062f \u0646\u0639\u0645\u062a\u200c\u0627\u0644\u0644\u0647\u06cc<\/a><\/p>\n

\u0634\u06cc\u0631\u06cc\u0646 \u0639\u0633\u0644\u06cc \u06a9\u0647 \u067e\u06cc\u06af\u06cc\u0631 \u0646\u0628\u0648\u062f<\/a><\/strong><\/p>\n

\u0645\u0642\u062f\u0627\u0631 dp_{state, rem}<\/span> \u0631\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645: \u062c\u0648\u0627\u0628 \u0645\u0633\u0626\u0644\u0647 \u0627\u06af\u0631 \u0627\u0632 \u0648\u0636\u0639\u06cc\u062a state<\/span> \u0634\u0631\u0648\u0639 \u06a9\u0646\u06cc\u0645 \u0648 rem<\/span> \u062d\u0631\u0641 \u0622\u062e\u0631 \u0646\u0627\u0645\u0647 \u0631\u0627 \u0628\u0647 \u0639\u0646\u0648\u0627\u0646 \u062e\u0631\u0648\u062c\u06cc \u0628\u062e\u0648\u0627\u0647\u06cc\u0645.<\/p>\n

\u06cc\u06a9 \u06af\u0631\u0627\u0641 \u0628\u0627 \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u062c\u0647\u062a\u200c\u062f\u0627\u0631 \u0648 \u0628\u06cc\u200c\u0648\u0632\u0646 \u062f\u0631\u00a0\u200c\u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f \u06a9\u0647 \u0631\u0627\u0633\u200c\u0647\u0627\u06cc \u0622\u0646 \u0647\u0627 \u062c\u0641\u062a\u200c\u0647\u0627\u06cc (state, rem)<\/span>\u00a0\u0647\u0633\u062a\u0646\u062f \u0648 \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc\u00a0\u200c\u0622\u0646 \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u200c\u0634\u0648\u0646\u062f.<\/p>\n

\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0645\u0642\u062f\u0627\u0631\u00a01 \\le rem \\le |s|<\/span> \u0648 \u06a9\u0627\u0631\u0627\u06a9\u062a\u0631\u00a0c<\/span>:<\/p>\n

    \n
  1. \u0627\u06af\u0631 \u0642\u0627\u0646\u0648\u0646\u06cc \u0628\u0635\u0648\u0631\u062a\u00a0state\\ state2\\ c<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u060c \u0622\u0646\u200c\u06af\u0627\u0647 \u06cc\u06a9 \u06cc\u0627\u0644 \u0627\u0632 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631\u00a0(state, rem)<\/span> \u0628\u0647 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631\u00a0(state2, rem)<\/span> \u0645\u06cc\u200c\u06af\u0630\u0627\u0631\u06cc\u0645.<\/li>\n
  2. \u0627\u06af\u0631\u00a0c = s_{|s| - rem}<\/span> \u0648 \u0642\u0627\u0646\u0648\u0646\u06cc \u0645\u062b\u0644\u00a0state\\ state2\\ c<\/span> \u0648\u062c\u0648\u062f \u0646\u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u06cc\u06a9 \u06cc\u0627\u0644 \u0627\u0632 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631\u00a0(state, rem)<\/span> \u0628\u0647 \u0631\u0627\u0633 \u0645\u062a\u0646\u0627\u0638\u0631\u00a0(state, rem - 1)<\/span> \u0645\u06cc\u200c\u06af\u0630\u0627\u0631\u06cc\u0645.<\/li>\n<\/ol>\n

    \u062d\u0627\u0644\u0627 \u0627\u06af\u0631 \u0627\u0632 \u0631\u0627\u0633 (1, |s|)<\/span>\u060c bfs<\/span> \u0628\u0632\u0646\u06cc\u0645 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0645\u0642\u062f\u0627\u0631 \u0647\u0645\u0647\u200c\u06cc \u062e\u0627\u0646\u0647\u200c\u0647\u0627\u06cc \u0631\u0627 \u062d\u0633\u0627\u0628 \u06a9\u0646\u06cc\u0645 \u0648 \u062f\u0631 \u0622\u062e\u0631 \u062c\u0648\u0627\u0628 \u0628\u0631\u0627\u0628\u0631 \u06a9\u0648\u0686\u06a9\u200c\u062a\u0631\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631 dp_{state, 0}<\/span> \u0628\u0631\u0627\u06cc state<\/span>\u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641 \u0627\u0633\u062a.<\/p>\n

    \u06a9\u062f ++C \u0627\u0632 \u062d\u0645\u06cc\u062f\u0631\u0636\u0627 \u06a9\u0627\u0645\u06a9\u0627\u0631\u06cc<\/a>\u00a0\u06a9\u0647 \u0628\u0631\u0627\u06cc \u0628\u0631\u0648\u0632 \u06a9\u0631\u062f\u0646 \u0647\u0631 \u0644\u0627\u06cc\u0647 \u0627\u0632 \u0645\u0642\u0627\u062f\u06cc\u0631\u00a0dp<\/span>\u060c \u0627\u0632\u00a0bfs<\/span> \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0631\u062f\u0647 \u0627\u0633\u062a.<\/p>\n

    \u06a9\u062f ++C \u0627\u0632 \u0645\u062d\u0645\u062f \u0635\u0627\u0646\u0639\u06cc\u0627\u0646<\/a> \u06a9\u0647 \u0631\u0627\u0647 \u06af\u0641\u062a\u0647\u200c\u0634\u062f\u0647 \u0631\u0627 \u067e\u06cc\u0627\u062f\u0647\u200c\u0633\u0627\u0632\u06cc \u06a9\u0631\u062f\u0647 \u0627\u0633\u062a.<\/p>\n

    \u0634\u06cc\u0631\u06cc\u0646 \u0639\u0633\u0644 \u0648 \u0639\u0644\u0648\u0645 \u062a\u062c\u0631\u0628\u06cc<\/a><\/strong><\/p>\n

    \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u06cc\u06a9 Heap<\/span>\u00a0\u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u062f\u0631 \u0622\u0646 \u0628\u0631\u0627\u06cc \u0647\u0631 \u0645\u0648\u0634 \u0627\u0648\u0644\u06cc\u0646 \u0631\u0648\u06cc \u06a9\u0647 \u0632\u0646\u062f\u0647 \u0646\u06cc\u0633\u062a \u0631\u0627 \u062f\u0631 \u0622\u0646 \u0646\u06af\u0647 \u0645\u06cc\u200c\u062f\u0627\u0631\u06cc\u0645 \u0648 \u06cc\u06a9 Segment\\ tree<\/span> \u0648 \u06cc\u0627 Fenwick\\ tree<\/span>\u00a0\u06a9\u0647 \u062a\u0639\u062f\u0627\u062f \u0645\u0648\u0634\u200c\u0647\u0627\u06cc \u0632\u0646\u062f\u0647\u200c\u06cc \u0647\u0631 \u0628\u0627\u0632\u0647 \u0631\u0627 \u0628\u0647 \u0645\u0627 \u0645\u06cc\u200c\u062f\u0647\u062f \u0648 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0648\u0636\u0639\u06cc\u062a \u0632\u0646\u062f\u0647 \u0634\u062f\u0646\u00a0\u0648 \u06cc\u0627 \u0645\u0631\u062f\u0646 \u0647\u0631 \u0645\u0648\u0634 \u0631\u0627 \u062f\u0631 \u0622\u0646 \u062a\u063a\u06cc\u06cc\u0631 \u062f\u0647\u06cc\u0645. \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0631\u062a\u06cc\u0628 \u062f\u0631 \u0627\u0648\u0644 \u0647\u0631 \u0631\u0648\u0632 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0627\u0632 \u0647\u06cc\u067e \u062a\u0645\u0627\u0645 \u0645\u0648\u0634\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u062f\u06cc\u0634\u0628 \u0645\u0631\u062f\u0647\u200c\u0627\u0646\u062f \u0631\u0627 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645 \u0648 \u062f\u0631 \u0641\u0646\u0648\u06cc\u06a9 \u062b\u0628\u062a \u06a9\u0646\u06cc\u0645 \u0648 \u0628\u0631\u0627\u06cc \u0647\u0631 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0633\u0648\u0627\u0644\u06cc \u0628\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0627\u0632 \u0641\u0646\u0648\u06cc\u06a9 \u067e\u0627\u0633\u062e \u0631\u0627 \u0628\u0647\u00a0\u200c\u062f\u0633\u062a \u0628\u06cc\u0627\u0648\u0631\u06cc\u0645 \u0648 \u0628\u0631\u0627\u06cc \u0647\u0631 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0627\u0646\u062a\u0642\u0627\u0642 \u0648\u06cc\u0631\u0648\u0633 \u0645\u0642\u0627\u062f\u06cc\u0631 \u0627\u0648\u0644\u06cc\u0646 \u0631\u0648\u0632 \u0632\u0646\u062f\u0647 \u0646\u0628\u0648\u062f \u0631\u0627 \u062f\u0631 Heap<\/span> \u0622\u067e\u062f\u06cc\u062a \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645.<\/p>\n

    \u06a9\u062f ++C \u0627\u0632 \u0645\u062d\u0645\u062f \u0646\u0639\u0645\u062a\u200c\u0627\u0644\u0644\u0647\u06cc<\/a><\/p>\n

    \u0634\u06cc\u0631\u06cc\u0646 \u0639\u0633\u0644 \u0648 \u0639\u0644\u0648\u0645 \u062e\u0641\u0646<\/strong><\/a><\/p>\n

    \u062a\u0639\u0627\u0631\u06cc\u0641:<\/p>\n

    Cildren(v)<\/span> \u0645\u062c\u0645\u0648\u0639\u0647\u200c\u06cc \u0628\u0686\u0647 \u0647\u0627\u06cc \u0631\u0627\u0633 v<\/span> \u0627\u0633\u062a \u0648 grandChildren(v)<\/span> \u0645\u062c\u0645\u0648\u0639\u0647\u200c\u06cc \u0631\u0626\u0648\u0633 \u062f\u0627\u062e\u0644 \u0632\u06cc\u0631\u062f\u0631\u062e\u062a v<\/span>.<\/p>\n

    \u0644\u0645\u06f1:\u00a0<\/strong><\/p>\n

    \\sum_{A \\subseteq grandChildren(v)}^{A\\neq \\varnothing}(\\prod_{u \\in A}^{}f(u)) <\/span><\/p>\n

    = \\prod_{u\\in grandChildren(v)}^{}(f(u) + 1) - 1 <\/span><\/p>\n

    = \\prod_{u \\in Children(v)}^{} (f(u) + 1)^{2} - 1<\/span><\/p>\n

    \u067e\u0633<\/p>\n

    \u00a0\\log_{2}{f(v) + 1} = \\sum_{u \\in Children(v)}^{}2\\log_{2}{(f(u) + 1)}<\/span><\/p>\n

    \u067e\u0633 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u0645\u00a0dp_v<\/span> \u0628\u0631\u0627\u0628\u0631\u00a0\\log_{2}{f(v) + 1}<\/span>. \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0631\u062a\u06cc\u0628\u060c \u06a9\u0645\u062a\u0631\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631\u00a0g<\/span> \u0631\u0648\u06cc \u0631\u0626\u0648\u0633 \u062f\u0631\u062e\u062a \u0647\u0633\u062a\u06cc\u0645 \u0648 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u0645:<\/p>\n

    \u00a0g(v) = \\sum_{u \\in Children(v)}^{}2g(u)<\/span><\/p>\n

    \u0627\u0645\u0627\u00a0\u0645\u0642\u062f\u0627\u0631\u00a0g<\/span> \u0631\u0648\u06cc \u0631\u0626\u0648\u0633 \u062f\u0631\u062e\u062a \u0628\u0633\u06cc\u0627\u0631 \u0628\u0632\u0631\u06af \u0627\u0633\u062a\u061b \u0628\u06cc\u0634 \u0627\u0632 \u062f\u0648 \u0628\u0647 \u062a\u0648\u0627\u0646 \u0627\u0631\u062a\u0641\u0627\u0639 \u062f\u0631\u062e\u062a!<\/p>\n

    \u0644\u0645 \u06f2: \u00a0<\/strong>\u0627\u06af\u0631 \u0647\u0631 \u06cc\u0627\u0644 \u0631\u0627 \u0627\u0632 \u0631\u0627\u0633\u06cc \u06a9\u0647 \u0627\u06af\u0631 \u0627\u0632 \u0627\u0648\u0646 \u0631\u06cc\u0634\u0647 \u062f\u0627\u0631 \u06a9\u0646\u06cc\u0645 \u062c\u0648\u0627\u0628 \u0628\u062f\u062a\u0631 \u0645\u06cc\u0634\u0648\u062f \u0628\u0647 \u0633\u0631 \u062f\u06cc\u06af\u0631 \u06cc\u0627\u0644\u00a0\u062c\u0647\u062a \u062f\u0627\u0631 \u06a9\u0646\u06cc\u0645\u060c \u0647\u0631 \u0631\u0627\u0633 \u0628\u0647 \u062c\u0632 \u0631\u0627\u0633 \u062c\u0648\u0627\u0628 \u06cc\u06a9 \u06cc\u0627\u0644 \u062e\u0631\u0648\u062c\u06cc \u062e\u0648\u0627\u0647\u0646\u062f \u062f\u0627\u0634\u062a \u0648 \u0647\u0645\u0647 \u06cc \u0645\u0633\u06cc\u0631\u0627\u06cc \u062c\u0647\u062a \u062f\u0627\u0631 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0627\u0644 \u0628\u0647 \u0631\u0627\u0633\u0650 \u062c\u0648\u0627\u0628 \u062e\u062a\u0645 \u0645\u06cc\u0634\u0648\u0646\u062f. \u067e\u0633 \u06a9\u0627\u0641\u06cc\u0633\u062a \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u06cc\u0627\u0644 \u0628\u0641\u0647\u0645\u06cc\u0645\u00a0\u0645\u0642\u062f\u0627\u0631\u00a0g<\/span> \u0631\u0648\u06cc \u06a9\u062f\u0627\u0645 \u0633\u0631\u0634 \u06a9\u0645\u062a\u0631 \u0627\u0633\u062a.<\/p>\n

    \u0644\u0645 \u06f3: <\/strong>\u0627\u06af\u0631\u00a0\u0627\u0632 \u06cc\u06a9 \u0631\u0627\u0633 \u0631\u06cc\u0634\u0647 \u062f\u0627\u0631 \u06a9\u0631\u062f\u0647 \u0628\u0627\u0634\u06cc\u0645\u060c \u0647\u0631 \u0631\u0627\u0633 \u0627\u06af\u0631 \u06cc\u0627\u0644 \u062e\u0631\u0648\u062c\u06cc\u0634 \u0628\u0647 \u067e\u062f\u0631\u0634\u00a0\u0646\u0628\u0627\u0634\u062f \u0642\u0637\u0639\u0646 \u0628\u0647 \u0628\u0686\u0647\u200c\u0627\u06cc\u0633\u062a \u06a9\u0647 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645\u00a0\u0639\u062f\u062f \u0628\u06cc\u0646 \u0628\u0686\u0647\u200c\u0647\u0627 \u0631\u0627 \u062f\u0627\u0631\u062f. (\u0627\u06af\u0631 \u0647\u0645 \u062f\u0648\u062a\u0627 \u0628\u0686\u0647 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0639\u062f\u062f \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u0646\u062f\u060c \u0642\u0637\u0639\u0646 \u06cc\u0627\u0644 \u062e\u0631\u0648\u062c\u06cc \u06cc\u0627 \u0628\u0647 \u067e\u062f\u0631 \u0627\u06cc\u0646 \u0631\u0627\u0633 \u0627\u0633\u062a \u0648 \u06cc\u0627\u00a0\u0627\u06cc\u0646 \u0628\u0647\u062a\u0631\u06cc\u0646 \u0631\u0627\u0633 \u0627\u0633\u062a.)<\/p>\n

    \u0644\u0645 \u06f4:\u00a0<\/strong>\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u062f\u0631\u062e\u062a \u0631\u0627 \u0631\u06cc\u0634\u0647 \u062f\u0627\u0631 \u06a9\u0631\u062f\u0647 \u0628\u0627\u0634\u06cc\u0645 \u0648\u00a0g_1(v)<\/span> \u0631\u0627 \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u0645\u00a0\u0645\u0642\u062f\u0627\u0631\u00a0g(v)<\/span> \u0628\u0631\u0627\u06cc \u0632\u06cc\u0631\u062f\u0631\u062e\u062a\u00a0v<\/span> \u0648 Leaves(v)<\/span> \u0645\u062c\u0645\u0648\u0639\u0647\u200c\u06cc \u0628\u0631\u06af\u200c\u0647\u0627\u06cc \u0632\u06cc\u0631\u062f\u0631\u062e\u062a v<\/span> \u0627\u0633\u062a. \u0647\u0645\u200c\u0686\u0646\u06cc\u0646 dist(u, v)<\/span> \u0628\u0631\u0627\u0628\u0631 \u0641\u0627\u0635\u0644\u0647\u200c\u06cc \u0631\u0627\u0633 u<\/span> \u0648 v<\/span> \u062f\u0631 \u062f\u0631\u062e\u062a \u0627\u0633\u062a. \u062f\u0627\u0631\u06cc\u0645:<\/p>\n

    g1(v) = \\sum_{u \\in Leaves(v)} 2^{dist(u, v)}<\/span><\/p>\n

    \u062f\u0631 \u0627\u062f\u0627\u0645\u0647 \u0628\u0648\u0633\u06cc\u0644\u0647\u200c\u06cc dfs\u00a0\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062c\u0647\u062a \u0647\u0631 \u06cc\u0627\u0644 \u0628\u0635\u0648\u0631\u062a \u06af\u0641\u062a\u0647\u200c\u0634\u062f\u0647 \u0631\u0627 \u062f\u0631 \u062f\u0631\u062e\u062a \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f\u061b \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u06a9\u0647 \u0627\u06af\u0631 \u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u0622\u0646 \u0631\u0627\u0633 \u06cc\u0627\u0644 \u062e\u0631\u0648\u062c\u06cc \u0628\u0647 \u06cc\u06a9\u06cc \u0627\u0632 \u0628\u0686\u0647\u200c\u0647\u0627\u06cc\u0634 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u0628\u0647 \u06a9\u062f\u0627\u0645\u06cc\u06a9 \u0627\u0632 \u0622\u0646\u200c\u0647\u0627 \u062e\u0648\u0627\u0647\u062f \u062f\u0627\u0634\u062a. \u0628\u0631\u0627\u06cc \u0646\u06af\u0647\u062f\u0627\u0634\u062a\u0646 \u0645\u0642\u062f\u0627\u0631\u00a0g1<\/span> \u0628\u0631\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0646\u06cc\u0632 \u062f\u0631 \u06cc\u06a9\u00a0set<\/span> \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0628\u06cc\u062a\u200c\u0647\u0627\u06cc \u06cc\u06a9 \u0645\u0642\u062f\u0627\u0631\u00a0g1(v)<\/span> \u0631\u0627 \u0646\u06af\u0647\u062f\u0627\u0631\u06cc \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u0648 \u0628\u0631\u0627\u06cc \u062c\u0645\u0639 \u06a9\u0631\u062f\u0646 \u062f\u0648 \u0645\u0642\u062f\u0627\u0631 \u0627\u0632 \u0645\u062c\u0645\u0648\u0639\u0647\u200c\u06cc \u06a9\u0648\u0686\u06a9\u062a\u0631 \u0645\u0642\u0627\u062f\u06cc\u0631 \u0631\u0627 \u0628\u0647 \u0645\u062c\u0645\u0648\u0639\u0647\u200c\u06cc \u0628\u0632\u0631\u06af\u062a\u0631 \u0627\u0646\u062a\u0642\u0627\u0644 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645. \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062c\u0648\u0631\u06cc \u0628\u0627 \u062f\u0642\u062a \u0627\u06cc\u0646 \u0628\u062e\u0634 \u0631\u0627 \u067e\u06cc\u0627\u062f\u0647\u200c\u0633\u0627\u0632\u06cc \u06a9\u0631\u062f \u06a9\u0647 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc \u0627\u06cc\u0646 \u0628\u062e\u0634 \u0627\u0632 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u00a0O(n\\log^2(n))<\/span> \u0634\u0648\u062f \u0648 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0628\u0631\u0627\u06cc \u0631\u0627\u0633 \u0631\u06cc\u0634\u0647 \u0645\u0642\u062f\u0627\u0631\u00a0g<\/span>\u00a0\u0645\u062d\u0627\u0633\u0628\u0647 \u0634\u0648\u062f.<\/p>\n

    \u0633\u067e\u0633 \u0645\u0633\u06cc\u0631 \u062c\u0647\u062a \u062f\u0627\u0631 \u0628\u062f\u0633\u062a \u0622\u0645\u062f\u0647 \u0627\u0632 \u0631\u06cc\u0634\u0647\u200c\u06cc \u062f\u0631\u062e\u062a \u062a\u0627 \u06cc\u06a9\u06cc \u0627\u0632 \u0628\u0631\u06af\u200c\u0647\u0627 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc\u200c\u06af\u06cc\u0631\u06cc\u0645\u061b \u0631\u0627\u0633 \u062c\u0648\u0627\u0628 \u062d\u062a\u0645\u0646 \u0631\u0648\u06cc \u0627\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0642\u0631\u0627\u0631 \u062f\u0627\u0631\u062f. \u0633\u067e\u0633 \u0628\u0627 \u0628\u0627\u06cc\u0646\u0631\u06cc \u0633\u0631\u0686 \u0631\u0648\u06cc \u0627\u06cc\u0646 \u0645\u0633\u06cc\u0631\u060c \u0631\u0627\u0633\u06cc \u06a9\u0647 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u06cc\u0627\u0644\u200c\u0647\u0627 \u0628\u0647 \u0633\u0645\u062a \u0627\u0648 \u062e\u0648\u0627\u0647\u0646\u062f \u0628\u0648\u062f \u0631\u0627 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f \u0648 \u0628\u0627 \u0645\u062d\u0627\u0633\u0628\u0647\u200c\u06cc \u0645\u0642\u062f\u0627\u0631\u00a0f<\/span> \u0631\u0648\u06cc \u0627\u06cc\u0646 \u0631\u0627\u0633 \u0628\u0648\u0633\u06cc\u0644\u0647\u200c\u06cc \u0631\u0648\u0634 \u06af\u0641\u062a\u0647 \u0634\u062f\u0647 \u062f\u0631 \u0644\u0645 \u06f1\u060c \u067e\u0627\u0633\u062e \u0646\u0647\u0627\u06cc\u06cc \u0631\u0627 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f.<\/p>\n

    \u06a9\u062f ++C<\/a><\/p>\n

    \u0645\u0648\u0641\u0642 \u0628\u0627\u0634\u06cc\u062f! \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"

    \u06cc\u0647 \u06a9\u0645 \u062f\u06cc\u0631 \u0634\u062f \u0648\u0644\u06cc \u0627\u0645\u06cc\u062f \u0648\u0627\u0631\u0645 \u0627\u0632 \u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627 \u0644\u0630\u062a \u0628\u0628\u0631\u06cc\u062f (\u0645\u062b \u0633\u0648\u0627\u0644\u0627 \u06a9\u0647 \u0644\u0630\u062a \u0628\u0631\u062f\u06cc\u062f ?). \u0631\u0627\u0647 \u062d\u0644 \u0647\u0627…<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,50,141],"tags":[],"class_list":["post-2307","post","type-post","status-publish","format-standard","hentry","category-developer","category-quera-developer","category-contests-and-events"],"_links":{"self":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2307","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/comments?post=2307"}],"version-history":[{"count":0,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2307\/revisions"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=2307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=2307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=2307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}