Light OJ - 1355 - Game of CS Tutorial

প্রব্লেমটি Green Hackenbush এর সুন্দর একটি প্রব্লেম। প্রব্লেম পড়ে থাকলে এবং Green Hackenbush বুঝে থাকলে, এটুকু নিশ্চয়ই বুঝেছো যে ১ একক দৈর্ঘ্যের এজ গুলো নিয়ে কোন সমস্যা নেই। বিপত্তি শুরু হয় যখন এজ এর দৈর্ঘ্য ১ এর বেশি হয়। 

কয়েকটি কেস এনালাইসিস করলে বুঝবে যে যেসব এজ এর দৈর্ঘ্য এক এর বেশি তারা একটি লুপ এর মতো কাজ করে। অর্থাৎ, x>1 দৈর্ঘ্যের একটি এজকে আমি x সংখ্যক একক দৈর্ঘ্যের এজ দ্বারা রিপ্লেস করতে পারি। 

এখন, একটি এজ [u,v] এর জন্য হিসেবটা কেমন হবে? 

১) যদি এজটির কস্ট = ১ হয়, তাহলে value[u] ^= (1 + value[v])

২) অন্যথায়, 

        i) কস্ট যদি বিজোড় হয়, তাহলে value[u] ^= (1 ^ value[v])       (Think about it by pen & papper)

        ii) কস্ট যদি জোড় হয়, তাহলে value[u] ^= value[v]

আশা করি এখন প্রব্লেমটি তোমার কাছে একটি স্ট্রেইট ফরোয়ার্ড প্রবেলেমে রূপান্তরিত হয়েছে। তাও না পারলে সলুশন দেখতে পারো।