Problem A :
এইখানে বলা হইছে X = 0 , আমাকে বিভিন্ন pre or post increment or decrement operation দেওয়া হবে আমাকে শেষ X এর ভ্যালু বলতে হবে । এইখানে টেস্টকেস দেওয়া আছে , আমাকে ফাস্ট এ টেস্ট কেস ইনপুট নিতে হবে তারপর একটা একটা করে srting input নিব এইখানে আমাদের খালি চেক করতে হবে কোন + sign আছে কিনা থাকলে ভ্যালু বাড়াব না হলে কমবে ।Problem B :
পিয়াস এর কোড
এইটাও অনেক সহজ প্রবলেম ।এইখানে বলা হইছে আমাকে একটা srting ইনপুট দিবে আমাকে বলতে হবে এইখানে কয়টা word আছে । এইখানে আমাকে EOF পর্যন্ত ইনপুট নিতে হবে । তারপর আমাকে প্রতিটা ইনপুট এর জন্য Word count করে প্রিন্ট করতে হবে ।Problem C :
say string inp ;
getline( cin , inp ) ;
int i , Ans = 0 , sz = inp.size() ; // string এর সাইজ দেয়
for ( i = 0 ; i < sz ; i++ )
{
if( i && !isalpha(inp[i]) && isalpha(inp[i-1]) Ans++ ; // এর মানে হইল এই লেটারটা কোন Alphabet না কিন্তু আগের লেটার টা ছিল মানে আমি একটা word পেয়েছি
}
print --- > Ans ;
টেস্ট কেস এর প্রবলেম । এইখানে আমাকে একটা বৃত্ত এর ব্যাসার্ধ দিবে যা একটা চতুর্ভুজ এর ভিতর এর সব বাহুকে স্পর্শ করে যাছে আমাকে এর শেড করা জায়গার Area বলতে হবে । ফরমুলাটা হইল যদি radius --> r then
area = ( 4 * r * r ) - 2 pi r * r ; // proof নিজে নিজে কর ।
Problem D :
triangle print এর প্রবলেম । ১/১ এ ল্যাবে স্যার এর অনেক প্রিয় Assignment । এই প্রবলেম এ New লাইন এর অনেক প্রবলেম হয় । এইখানে এই ব্যাপারটা সবার খেয়াল করতে হবে ।
NOTE: There is a blank line after each separate waveform, excluding the last one.এর মানে হইল সব কেস এর পর আমি একটা extra new line print দিব কিন্তু লাস্ট কেস এ দিব না । এইটা আমাকে চেক রাখতে হবে ।
সিফাত এর কোড
Problem E :
এইখানে আমাকে দুইটা নাম্বার দিবে n , m . আমাকে তারপর n টা সংখ্যা দিবে যাদের থেকে আমি m টা সংখ্যা নিব । কিন্তু এমন ভাবে এই m গুলার সংখ্যার মধ্যে maximum আর minimum এর difference হবে minimum .
sorting এর প্রবলেম । আমি nটা নাম্বার sort করব তারপর m টা number এর মধ্যে Ans বের করব।
int n , m , i ;
cin >> n >> m ;
for ( i = 0 ; i < n ; i++ ) cin >> Inp[i] ; // Inp --> Array globally declear
sort( Inp , Inp+n ) ; // sort ascending order
int Ans = Inp[m-1] - Inp[0] ; // initial value
for ( i = 1 ; i + m - 1 < n ; i++ )
if ( Inp[i+m-1] - Inp[i] < Ans ) // Value update
Ans = Inp[i+m-1] - Inp[i] ;
print --- > Ans ;
Problem F :
এইটা DP এর basic state reduction problem । এইখানে চারটা নোড দেওয়া হইছে A , B , C , D . প্রাথমিক ভাবে পিপড়াটা আছে D তে । আমাকে একটা নাম্বার n দেওয়া হবে । আমাকে count করে বলতে হবে n length এর কয়টা cyclic path আছে । cyclic path মানে যেখানে ছিলাম আবার সেখানেই আসব । এইখানে D থেকে D তেই আসব কয়ভাবে ( কয়টা Unique path আছে ) । যেমন n== 2 হলে
- D - A - D
- D - B - D
- D - C - D
এমন ৩টা path আছে । এখন আসি space reduction dp কি ? Dp তে আসলে আমরা কি করি state by state value calculate করি । কোন state এর value তার আগের এক বা একাধিক state থেকে পাই । যদি এমন দেখা যায় একটা state এর ভাল্যু খালি তার আগের এক/দুই/তিন ( মানে fixed অল্প কিছু state ) এর উপর depend করে তাইলে আমি আগের state এর ভ্যালু বাদ দিতে পারি । এই প্রবলেম এর জন্য দেখি কিভাবে ? এইখানে ০ length এর খালি একটা cyclic path এই আছে ।
0 মানে পিপড়া D তে ছিল D তেই আছে । এখন যদি 1 length এর বের করতে চাই তাহলে কিভাবে । আসলে 1 length এর cyclic path মানে o length এর A তে total cyclic path + 0 length এর B তে total cyclic path + 0 length এর C এর total cyclic path .
মানে আসলে এমন । 2 length এর calculation এর জন্য খালি 1 length এর state এর ভ্যালু দরকার আমার । তাই 2 length এর জন্য 0 length এর ভ্যালু আমার মেমু করে রাখার কোন দরকার নাই ।
dp[now][ node == D here ] = ( dp[prev][A] + dp[prev][B] + dp[prev][C] ) % Mod
এখন প্রতি state শেষ এ আমি now , prev এর ভ্যালু চেঞ্জ করব । এইটা কিভাবে কাজ করছে তা খাতা কলমে করে দেখ ।
long long dp[4][2] ;
dp[0][0] = dp[1][0] = dp[2][0] = 0 ;
dp[3][0] = 1 ;
int n , i ;
cin >> n ;
int now = 1 ;
int prv = 0 ;
for ( i = 1 ; i <= n ; i++ )
{
dp[0][now] = (dp[1][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
dp[1][now] = (dp[0][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
dp[2][now] = (dp[0][prv] + dp[1][prv] + dp[3][prv] )%Mod ;
dp[3][now] = (dp[0][prv] + dp[2][prv] + dp[1][prv] )%Mod ;
swap(now,prv);
}
cout << dp[3][prv] << endl ;
Problem G :
এই প্রবলেমটা কিছুদিন আগেই CF এর কনটেস্ট এর ছিল । আমি প্রবলেমটা ভালমত না পড়ার কারনে মিস করে গেছিলাম ।এইটার Dp এবং Directed graph এর longest path দুইটাই solution আছে ।আমি গ্রাফ এর প্রসেসটা বলি । এইখানে আমাকে n length এর m সংখ্যক Array দেওয়া হইছে । আমাকে এই m Array এর মধ্যে longest common subsequence এর বলতে হবে । এইখানে সবচেয়ে Important point" Each of them consists of numbers 1, 2, ..., n in some order."
এর মানে হইল n এর যে ভ্যালু থাকবে Array তে 1 - n পর্যন্তই থাকবে যেকোন order এ । এইখানে n এর লিমিট ১০০০ আমি যদি এখন এদের কে directed graph এ convert করতে পারি তাহলে আমার খালি longest path এর lengthটাই আমার উত্তর । ১০০০ যেহেতু লিমিট আমি খুব সহজেই n^2 , m <= 5 এর মধ্যে চেক করতে পারি দুইটা index i & j এর জন্য সব Array তেই i এর পর j আছে কিনা । যদি থাকে তাহলে i --> j path থাকবে । graph বানানো হইলে আমাকে জাস্ট বের করতে হবে maximum length এর path যেইটা Dfs দিয়ে সবাই পারবে আশা রাখি ।
const int MX = 1005 ;
vector < int > G[MX] ;
int pos[10][MX] , Best[MX] , Inp[10][MX];
int N , K ;
bool used[MX];
int Ans ;
void Dfs(int node)
{
used[node] = 1 ;
// Best[node] = 1 ;
int sz = G[node].size();
int i ;
for ( i = 0 ; i < sz ; i++ )
{
int u = G[node][i];
if( !used[u] ) // already visited
Dfs(u);
Best[node] = max( Best[node] , Best[u] + 1 ) ;
}
Best[node] = max(Best[node] , 1 );
Ans = max( Ans , Best[node]);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int i , j , k , n ;
cin >> N >> K ;
for ( i = 1 ; i <= K ; i++ )
{
for ( j = 0 ; j < N ; j++ )
{
cin >> Inp[i][j] ;
pos[i][Inp[i][j]] = j+1 ;
}
}
bool thik ;
// now graph construct
for ( i = 1 ; i <= N ; i++ )
{
for ( j = 1 ; j <= N ; j++ )
{
if ( i == j ) continue ;// no self loop possible
// now we check if its possible to have a edge for i to j
// its only possible if j is after i in every set
thik= 1 ;
for ( k = 1 ; k <= K && thik ; k++ )
{
if ( pos[k][j] <= pos[k][i] )
thik = 0 ; // not possible t
}
if ( thik ) G[i].pb(j);
}
}
Ans = 0 ;
for ( i = 1 ; i <= N ; i++ )
{
if( !used[i] ) Dfs(i);
}
cout << Ans << endl ;
Problem H :
এইটা Interval scheduling ( Greedy ) problem . এইখানে অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা wrapper program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম wrapper program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে ।
struct abc
{
int value , mark ; // mark 0 for start point , 1 for end
} Inp [ Mx + Mx ] ;
bool cmp ( abc A , abc B )
{
if ( A.value == B.value ) return A.mark < B.mark ; // start mark age thakbe
return A.value < B.value ;
}
int main()
{
int n , i , x , y , idx = 0;
cin >> n ;
for ( i = 0 ; i < n ; i++ )
{
cin >> x >> y ;
Inp[idx].value = x ;
Inp[idx++].mark = 0 ;
Inp[idx].value = y ;
Inp[idx++].mark = 1 ;
}
sort(Inp , Inp+idx , cmp );
int Ans = -Inf ;
int cur = 0 ; // eita count korbe koyta program ekhon run korche
for ( i = 0 ; i < idx ; i++ )
{
if( Inp[i].mark == 0 ) // mane notun program start hoiche
cur++;
else cur-- ; // program off hoiche
Ans = max(Ans , cur );
}
print -- > Ans ;
return 0 ;
}
কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans .
যে যে প্রবলেম সল্ভ করা যায়নি কনটেস্ট টাইমে তা upsolving ( কনটেস্ট এর পর সল্ভ ) করতে হবে । না হলে আসলে কিছুই শিখা হবে না । সবার জন্য শুভ কামনা :)
ভাই আপনি যে প্রব্লেম লিঙ্ক গুলা দিছেন ঐ গুলা শো করতেছে না
ReplyDeleteকনটেস্ট টা তো hust এ দেওয়া হইছিল , কোন কারণে hust এখন down এইটা কারণ হতে পারে । একটু পরই হয়তো ঠিক হয়ে যাবে ।
ReplyDelete