LightOj 1374 / LiveArchive 6963 (Confusion in the Problemset) solution

প্রোবলেমের সংক্ষিপ্ত বর্ণনাঃ

কিছু পেজ প্রিন্ট করা হয়েছে, কিন্তু পেজ নাম্বার ভুল প্রিন্ট করা আছে ।
প্রোবলেমে বলা আছে, মোট কত গুলো পেজ আছে আর কোন পেজে পেজ নং কত প্রিন্ট করা আছে ।

আউটপুটে বলতে হবে, পেজ গুলোকে কি এমনভাবে সাজানো যাবে, যাতে করে ঐ পেজের নাম্বার পেজের আগে কত গুলো পেজ আছে তা বুঝাবে অথবা ঐ পেজের পরে কত গুলো পেজ আছে তা বুঝাবে ?

যদি এমন ভাবে সাজানো যায়, তবে "yes" প্রিন্ট করতে হবে, নতুবা "no" প্রিন্ট করতে হবে ।

সমাধানঃ

ধর, তোমার কাছে মোট ৪টা পেজ আছে ।

যেহেতু, ১ম পেজের আগে ০ টা পেজ আছে, পরে ৩ টা পেজ আছে, তাই নিয়ম অনুযায়ী এই পেজে যদি 0 বা 3 প্রিন্ট করা থাকে তবে তা সঠিক বলে ধরা হবে । তাই ১ম পেজটা এমন পেজ হতে হবে, যেই পেজে পেজ নাম্বার 0 বা 1 প্রিন্ট করা আছে ।

একইভাবে, ২য় পেজ হিসেবে রাখতে হবে এমন পেজ, যেই পেজে 1 বা 2 প্রিন্ট করা আছে । কারণ, ২য় পেজের আগে ১টি পেজ(১ম পেজ) আর পরে আরো ২ টি পেজ আছে(৩য় ও ৪র্থ পেজ)।

৩য় পেজের আগে আছে ২টি পেজ(১ম পেজ ও ২য় পেজ), আর পরে আছে ১ টি পেজ(৪র্থ পেজ) । তাই এই পেজের পেজ নাম্বার হতে হবে 2 বা 1 ।

৪র্থ পেজের আগে আছে ৩টি পেজ(১ম, ২য় ও ৩য় পেজ),  আর পরে আছে ০ টি পেজ । তাই এই পেজের পেজ নাম্বার হতে হবে 4 বা 0 ।

তাহলে, এক কথায় আমরা কি বলতে পারি ?

যদি n সংখ্যক পেজ থাকে তবে -

১ম পেজের আগে থাকবে ০ টি পেজ, পরে থাকবে n-1 সংখ্যক পেজ (প্রিন্ট করতে হবে 0 বা n-1)

২য় পেজের আগে থাকবে ১ টি পেজ, পরে থাকবে n-2 সংখ্যক পেজ  (প্রিন্ট করতে হবে 1 বা n-2)

৩য় পেজের আগে থাকবে ২ টি পেজ, পরে থাকবে n-3 সংখ্যক পেজ  (প্রিন্ট করতে হবে 2 বা n-2)
....................................................................................................................
....................................................................................................................
....................................................................................................................

i তম পেজের আগে থাকবে i-1 সংখ্যক পেজ, পরে থাকবে n-i সংখ্যক পেজ (প্রিন্ট করতে হবে i-1 বা n-i)

.......................................................................................................................
n তম পেজের আগে থাকবে n-1 সংখ্যক পেজ, পরে থাকবে n-n=0 সংখ্যক পেজ । (প্রিন্ট করতে হবে n-1 বা 0)।

অতএব, আমরা এখন জানি কোন পেজে পেজ নাম্বার কত প্রিন্ট করতে হবে ।

এখন যা জানা দরকার, তা হল, i তম পেজে পেজ নাম্বার যেহেতু 'i বা i-1' প্রিন্ট করতে হবে, আমাদের চেক করতে হবে, মোট যত গুলো পেজ আছে, তার মাঝে এমন কোন পেজ আছে কিনা যার পেজ নাম্বার 'i বা i-1' ।

সেটা কেমনে করব ? আমরা সবগুলো নাম্বার এক এক করে চেক করে দেখতে পারি যে এমন কোন পেজ নাম্বার পাওয়া যায় কিনা ।

কিন্তু প্রোবলেম এ বলা আছে, n মান হতে হতে পারে 10000 পর্যন্ত ! তাহলে প্রতি ইন্ডেক্সের মানের জন্য n সংখ্যক পেজের নাম্বার চেক করতে Time complexity হবে O(n^2) !!

আমরা কিভাবে এই Time complexity কমাতে পারি ??

আমরা যদি প্রথমেই একটা অ্যারে রাখতাম, যাতে কোন পেজ নাম্বার কত বার আছে তা থাকবে, তবে আমরা O(1) এই কিন্তু চেক করতে পারতাম, যে কাংখিত পেজ নাম্বার আছে কি নাই !!!
আর n সংখ্যক পেজের নাম্বার চেক করতে Time complexity হবে O(n) !!

আরেকটা ব্যাপার আছে, সেটা হলো - কোন পেজ নাম্বার আছে বলেই আমরা তা ইউস করতে পারব না কিন্তু !! কেন ? কেন ?? তা কেন ??? চিন্তা করে বল দেখি !

কারণ, ওই পেজ নাম্বারটা যদি আগেই ব্যবহার করে থাকি তবে তা পরে আবার কিভাবে ইউস করব ?
তবে হ্যা, আবারো ইউস করতে পারব, যদি ঐ পেজ নাম্বারটা একাধিক পেজে প্রিন্ট করা থেকে থাকে অর্থাৎ, একই পেজ নাম্বার যদি রিপিট থাকে । যেমন, ৩য় আর ৪র্থ পেজে ০ প্রিন্ট করা আছে, তাহলে আমরা এর একটা পেজ ১ম পেজ হিসেবে আরেকটা পেজ শেষ পেজ হিসেবে সাজাব !!

উদাহরণঃ
ধর, মোট পেজ আছে ৪টা আর পেজ নাম্বার গুলো এভাবে প্রিন্ট করা আছে -

এক্ষেত্রে আমাদের ans কী হবে ?

ans হবে 'yes' । 'yes' প্রিন্ট করতে হবে, কারণ আমরা পেজের নাম্বার গুলো এভাবে সাজাতে পারি -

আমরা কী করলাম ?

যেহেতু, মোট পেজ, n=4, তাই

১ম পেজে 1-1=0 বা 4-1=3 প্রিন্ট করতে হবে(কারণ, আগে আছে 0 টা পেজ, পরে আছে 3 টা পেজ), তাই ৩য় পেজটাকে এনে প্রথমে বসিয়ে দিলাম । কারণ, ৩য় পেজের পেজ নাম্বার লেখা আছে 3, (২য় পেজ বসালেও পারতাম, কারণ, ২য় পেজের নাম্বার প্রিন্ট করা আছে 0, একটা বসালেই হল )।

২য় পেজে প্রিন্ট করতে হবে 2-1=1 বা 4-2=2,(কারণ, আগে আছে ১ টা পেজ, পরে আছে ২ টা পেজ) তাই ৪র্থ পেজটাকে এনে ২য় পেজের স্থানে বসিয়ে দিলাম । কারণ, ৪র্থ পেজের পেজ নাম্বার লেখা আছে 1, (১ম পেজ বসালেও পারতাম, কারণ, ১ম পেজের নাম্বার প্রিন্ট করা আছে ২, একটা বসালেই হল )।

৩য় পেজে প্রিন্ট করতে হবে 3-1=2, বা 4-3=1, (কারণ, আগে আছে 2 টা পেজ, পরে আছে 1 টা পেজ) তাই ১ম পেজটাকে এনে ৩য় পেজের স্থানে বসিয়ে দিলাম । কারণ, ১ম পেজের পেজ নাম্বার লেখা আছে 2, (৪র্থ পেজ বসানো যেত,কারণ, ৪র্থ পেজের নাম্বার প্রিন্ট করা আছে 1, কিন্তু সেটা আগেই ২য় পেজের স্থানে বসিয়েছি)।

৪র্থ পেজে প্রিন্ট করতে হবে 4-1=3, বা 4-4=0, (কারণ, আগে আছে 3 টা পেজ, পরে আছে 0 টা পেজ) তাই ২য় পেজটাকে এনে ৪র্থ পেজের স্থানে বসিয়ে দিলাম । কারণ, ২য় পেজের পেজ নাম্বার লেখা আছে 0, (৩য় পেজ বসানো যেত,কারণ, ৩য় পেজের নাম্বার প্রিন্ট করা আছে 3, কিন্তু সেটা আগেই ১ম পেজের স্থানে বসিয়েছি)।

সব তো বলে ফেললাম, এবার তোমার কাজ হল, নিজে কোড টা লিখে ফেলা ! তাহলে ঝটপট কোড লিখে ফেল, আর অনলাইন জাজে সাবমিট করে ফেল !!

প্রোবলেম লিঙ্কঃ
LightOj 1374
ACM-ICPC Live Archive 5963

যদি কোড লিখতে সমস্যা হয় তার জন্য নিচে কোড দিয়ে দিলাম । তবে নিজে আগে চেস্টা না করে কোড দেখবে না । একান্তই না পারলে তখন হেল্প নিতে পার ।

Source Code:

	#include<bits/stdc++.h>
	using namespace std;
	int main()
	{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	int n, i, cas, t, page, have_page[10005];
	cin>>t;
	for(cas=1;cas<=t;cas++)
	{
	cin>>n;
	for(i=0;i<=n;i++)
	have_page[i]=0;
	for(i=0;i<n;i++)
	{
	cin>>page;
	if(page>=0 && page<=n)
	have_page[page]++;
	}
	int cnt = 0;
	for(i=0;i<n;i++)
	{
	if(have_page[i]>0)
	{
	cnt++;
	have_page[i]--;
	}
	else if(have_page[n-i-1]>0)
	{
	cnt++;
	have_page[n-i-1]--;
	}
	}
	if(cnt>=n)
	cout << "Case " << cas << ": yes\n";
	else cout << "Case " << cas << ": no\n";
	}
	return 0;
	}

view raw lightoj 1374.cpp hosted with ❤ by GitHub

বিঃদ্রঃ গত ১৯-০৫-২০১৬ তারিখে শ্রদ্বেয় Azad Abul Kalam স্যার আমাদের জন্য একটি কন্টেস্টের আয়োজন করেছিলেন, যেই কন্টেস্টের সাথে একই সময়ে, আমার একটি ইনকোর্স পরীক্ষার সময়ও পরে যায় । আমি কন্টেস্টে অংশ নেবার লোভ সামলাতে না পেরে - ইনকোর্স পরীক্ষা না দিয়ে কন্টেস্টে অংশ নেই :)

কন্টেস্টে মোট ছয়টি প্রোবলেমের মধ্যে সব চেয়ে মজার প্রোবলেম ছিল এটি, যেটি সলভ করে এত মজা পেয়েছিলাম যে, বলে বুঝাতে পারব না !! :) ইনকোর্সে ৫ এ ৫ পেলেও যে মজার কোটি ভাগের এক ভাগও পেতাম না । ফলে, ইনকোর্স পরীক্ষা না দিয়ে প্রোগ্রামিং কন্টেস্টে অংশ নেয়া সার্থক হয়েছিল, এই প্রোবলেমটি সলভ করতে পারায় :)

কন্টেস্টে ১ম, ২য় ও ৩য় স্থান অধিকারীর জন্য ছিল স্যারের পক্ষ থেকে আকর্ষণীয় পুরস্কার (টি-শার্ট, কলম ইত্যাদি)।

কন্টেস্টে এই প্রোবলেমটি শুধু আমিই সলভ করতে পেরেছিলাম, আর এজন্যই কন্টেস্টে আমার চ্যাম্পিয়ন হওয়াটাও সম্ভব হয়েছিল :) ইনকোর্স পরীক্ষা না দিয়ে প্রোগ্রামিং কন্টেস্টে অংশ নেয়াও সার্থক হয়েছিল :)

অতএব, প্রোবলেমটির বিশেষ মাহাত্ব্য রয়েছে :)