UVa 12890: Easy Peasy
statement: একটা array থাকবে সেখানে কতভাবে সেট করা যাবে যেন সেটের কোন ইলিমেন্ট রিপিট না হয়।
Technique: technique এর ব্যাখ্যার জন্য প্রথম টেস্ট কেস দিয়ে শুরু করি।
a[]={1,2,1}
আমরা একটা রিপিট ভ্যারিয়েবল রাখবো যেটা বলবে এই ভ্যালুটা আমার এতো নাম্বার ইনডেক্সে রিপিট হয়েছে।
প্রথমে আমরা যদি ডান পাশ থেকে শুরু করি ১ এর জন্য রিপিট ভ্যালু পাই নি। তাই ১ এর জন্য সেট সম্ভব ৩-২=১ টি। এখন ১ এর রিপিট ভ্যালু হিসেবে ইনডেক্স সেভ করে রাখবো ।
তারপর ২ এর জন্য কোন রিপিট ভ্যালু পাই নি তাহলে ২ এর সেট হবে ৩-১=২ টি (2,(2,1))।
২ এর জন্য একই ভাবে ইনডেক্স সেভ অরে রাখবো।
পুনরায় ১ এ আসার পর দেখছি এটি রিপিট হয়েছে এবং index 2 তে। তাহলে নিশ্চয় এটি ২ পর্যন্ত সেট করতে পারবে না। তাহলে ১ এর জন্য সেট হবে 1-0=1 টি ।
Critical Test Case: a[]={7,7,2,2}
এটার জন্য শুধু ওই ভ্যালুর রিপিট ইনডেক্স চেক করলে হবে না। সে জন্য আমি প্রথম যখন ৩-২=১ মানে ৩ টোটাল নাম্বার এর সাথে বিয়োগ করেছিলাম ।কিন্তু রিপিট ভ্যালু পেলে তখন সেটা আর টোটাল নাম্বার না হয়ে রিপিট ভ্যালু পর্যন্ত হবে। কারন এখানে আমার ৭ রিপিট না হলেও ২ কিন্তু রিপিট হয়ে গিয়েছিলো।
তাহলে sequence টা হবেঃ
2=> (4-3)=1; nxt=4;
2=>(3-2)=1; nxt=3; (যেহেতু ২ রিপিট )।
**7=>(3-1)=2; nxt=3;
7=>(1-0)=1; nxt=1;
Another Critical Test Case: 7 2 2 7 :)
Happy Coding :)
