دو رشته از حروف 'a' تا 'z' و '0' و '1' به طول یکسان به شما داده شده است. شما باید به جای حروف 'a' تا 'z' طوری ارقام '0' و '1' را جایگزین کنید که اختلاف دو عدد در مبنای دو کمینه شود.
در تنها سطر خروجی کمترین اختلاف ممکن بین دو عدد را بنویسید.
ورودی نمونه | خروجی نمونه |
---|---|
aaa bbb | 0 |
101 aaa | 2 |
10ab ab01 | 1 |
پاسخ
هر کدام از رشته ها را میتوان به صورت ضریبی از اعداد و متغیر ها نوشت، برای مثال:
$$'a1a0b' = b+20\times a+8$$
پس میتوان اختلاف بین دو عدد را هم به صورت یک عبارت بر حسب متغیرهای 'a' تا 'z' و اعداد نوشت. حال اگر اولین رقم ( از سمت چپ ) که این دو عدد در آن اختلاف دارند را مشخص کنیم، با در نظر گرفتن معادلاتی به صورت 'a'='b' یا 'a'=0 که از این فرض بهدست می آیند میتوانیم به صورت حریصانه Greedy-algorithm طوری اعداد 0 و 1 را به متغیرهای نسبت بدهیم که عدد کمتر را به عدد بیشتر نزدیک کنیم. پس کافیست از میان تمام فرض های ممکن حالتی که اختلاف دو عدد را کمینه میکند را بهدست بیاوریم.
راه حل دوم:
اگر اختلاف بین دو عدد را به صورت عبارتی بر حسب اعداد و متغیرهای 'a' تا 'z' بنویسیم، میتوانیم با چک کردن $2^{26}$ حالت نسبت دادن اعداد 0 و 1 به متغیرها مقدار کمینه رابهدستآوریم.زماناجرایاین الگوریتم زیاد است و نمیتوان با استفاده از آن سوال را در زمان مناسب حل کرد اما اگر متغیرها را به دو دسته 'a' تا 'l' و'm' تا 'z' تقیسم کنیمو به ازای هر دسته، تمام مقادیر بهدست آمدهاز نسبت دادناعداد $0$ و $1$ به متغیرها در عبارت را در یک Binary-search-tree ذخیره کنیم، میتوانیم به ازای هر حالت از یکدسته، حالتی از دسته دیگر که باعث میشود اختلاف دو عدد کمینه شود را در زمان لگاریتمی بهدست آوریم.
با استفاده از این روش که bidirectional backtracking نام دارد، میتوان جواب سوال را در زمان$o(2^{13} \times log(2^{13}))$ بهدست آورد.