All posts filed under “প্রবলেম সলভিং

comment 0

স্ট্যান্ডার্ড টেমপ্লেট লাইব্রেরী – ম্যাপ

এই মুহুর্তে আমরা একটা সাইটে ইউজার একাউন্ট রেজিস্টার সিস্টেম নিয়ে কাজ করতে চাচ্ছি। সিস্টেমের বেসিক কাজটা খুবই সোজা। প্রত্যেকবার একজন ইউজার রেজিস্টার করতে চাইলে, আমরা সিস্টেম ডাটাবেজ চেক করে দেখবো এ নামে কোন ইউজার আছে কিনা। যদি না থাকে, তাহলে ওই ইউজার রেজিস্টার হবেন এবং আমরা OK মেসেজ শো করবো। যদি নামটি আগেই আমাদের ডাটাবেজে থাকে, মানে এই নামে আগেই কেউ একজন রেজিস্টার করে ফেলেন সেক্ষেত্রে নতুন নামের ফরম্যাট হবে এরকম- ইন্টিজার ভেল্যু (1, 2, 3… ) ওই নামের শেষে যোগ হবে এবং ইউজারকে এই নামে রেজিস্ট্রেশন করার জন্য রিকমেন্ডেশন পাঠাবো। ধরা যাক, karim রেজিস্টেশন রিকেউয়েস্ট পাঠিয়েছে, এখন করিম নামে…

comment 1

SPOJ Problem ADFRUITS

এই প্রবলেমটি একটি স্ট্রেইট ফরোয়ার্ড Shortest Common Subsequence প্রবলেম । ডিরেক্ট Shortest Common Subsequence Algorithm প্রয়োগ করে কিংবা Longest Common Subsequence কে কিছুটা মডিফিকেশন করে এটি সলভ করা সম্ভব । ডাইনামিক প্রোগ্রামিংয়ের খুবই জনপ্রিয় এবং ক্লাসিক্যাল দুটি এলগরিদম হলো LCS ও SCS Algorithm । LCS বা SCS Algorithm কিভাবে কাজ করে তুমি যদি না জেনে থাকো তাহলে নিচের লিঙ্ক থেকে শিখে নিতে পার । খুব সহজ ভাষায় LCS হলো দুটি স্ট্রিংয়ের মধ্যে সবচে longest subsequece টি. দুটি স্ট্রিংয়ের lcs একটির বেশীও হতে পারে । যেমন – eye, eyes স্ট্রিং দুটির longest subsequence হলো eye. উইকিতে Shortest Common Subsequence এর বর্ণনা করা হয়েছে এভাবে – a shortest common supersequence of strings x and y is a shortest string z such that both x and y are subsequences of z. যেমন – স্ট্রিং ananas ও banana এর SCS হলো bananas।

comment 0

Tricks on array index range query

ধরা যাক, আমাদের কাছে ara[5] সাইজের একটা এরে আছে । আগেই বলে রাখছি, এরে ইনডেক্স শুরু হবে 1 থেকে, 0 থেকে না। আমাদের এই এরেতে ৭ বার কুয়েরি করতে হবে [x, y] ইন্টার্ভালে । প্রতি কুয়েরিতে ওই ইন্টার্ভালের ইনডেক্সগুলোতে 2 যোগ করতে হবে । কুয়েরি শেষে পরিবর্তিত array প্রিন্ট করতে হবে ।

ara[5] = {2, 3, 7, 4, 10}; // array input
// 07 queries
1 5
2 4
5 5
2 5

Problems on Dynamic Programming

SGU Problems :  269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494 http://www.spoj.com/problems/SAMER08D/ http://acm.sgu.ru/problem.php?contest=0&problem=199 http://www.spoj.com/problems/MDOLLS/ http://www.spoj.com/problems/MSTICK/ http://www.spoj.com/problems/MCARDS/ http://www.spoj.com/problems/MIXTURES/ http://www.spoj.com/problems/SCUBADIV/ http://z-trening.com/tasks.php?show_task=5000000355 http://z-trening.com/tasks.php?show_task=5000000286 http://z-trening.com/tasks.php?show_task=5000000465 http://z-trening.com/tasks.php?show_task=5000000310 http://z-trening.com/tasks.php?show_task=5000000778 http://z-trening.com/tasks.php?show_task=5000000363 http://z-trening.com/tasks.php?show_task=5000001024 http://www.spoj.com/problems/VOCV/ http://www.spoj.com/problems/PT07F/ http://www.spoj.com/problems/PT07X/ http://z-trening.com/tasks.php?show_task=5000000070 http://z-trening.com/tasks.php?show_task=5000000569 http://z-trening.com/tasks.php?show_task=5000000441 http://z-trening.com/tasks.php?show_task=5000000050 http://www.spoj.com/problems/RENT/ http://www.spoj.com/problems/INCSEQ/ http://www.spoj.com/problems/INCDSEQ/ http://z-trening.com/tasks.php?show_task=5000000624 http://z-trening.com/tasks.php?show_task=5000000742 http://z-trening.com/tasks.php?show_task=5000000749 http://z-trening.com/tasks.php?show_task=5000001044 http://www.spoj.com/problems/SEQ/ http://www.spoj.com/problems/SPP/ http://z-trening.com/tasks.php?show_task=5000000078 http://z-trening.com/tasks.php?show_task=5000000543 http://z-trening.com/tasks.php?show_task=5000000718 http://z-trening.com/tasks.php?show_task=5000000237 http://z-trening.com/tasks.php?show_task=5000000311 http://www.spoj.com/problems/MORSE/ (dp + trie) Very Hard. http://www.spoj.com/problems/MPOLY/ http://www.spoj.com/problems/CVXPOLY/ http://www.spoj.com/problems/MTRIAREA/ http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=2222 http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122 http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122 http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1125 Game (IOI 2008, Practice session) http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

comment 1

Problems on (segment trees, range queries, interval trees, k-d trees, Binary index trees)

http://www.spoj.com/problems/GSS1 http://www.spoj.com/problems/GSS2 http://www.spoj.com/problems/GSS3 http://www.spoj.com/problems/GSS4 http://www.spoj.com/problems/GSS5 http://www.spoj.com/problems/GSS6 http://www.spoj.com/problems/GSS7 http://www.spoj.com/problems/ANDROUND/ http://www.spoj.com/problems/BRCKTS/ http://www.spoj.com/problems/DQUERY/ http://www.spoj.com/problems/FREQUENT/ http://www.spoj.com/problems/HEAPULM/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/KGSS/ http://www.spoj.com/problems/MKTHNUM/ http://www.spoj.com/problems/NICEDAY/ http://www.spoj.com/problems/YODANESS/ http://www.spoj.pl/problems/INCSEQ/ http://www.spoj.pl/problems/INCDSEQ/ http://www.spoj.pl/problems/KQUERY/ http://www.spoj.pl/problems/QTREE/ http://www.spoj.pl/problems/QTREE2/ http://www.spoj.pl/problems/QTREE3/ http://www.spoj.com/problems/QTREE4/ http://www.spoj.com/problems/QTREE5/ http://www.spoj.pl/problems/CTRICK/ http://www.spoj.pl/problems/MATSUM/ http://www.spoj.pl/problems/RATING/ http://www.spoj.pl/problems/RRSCHED/ http://www.spoj.pl/problems/SUPPER/ http://www.spoj.pl/problems/ORDERS/ http://www.spoj.com/problems/MULTQ3/ http://www.spoj.com/problems/RPAR/ http://www.spoj.com/problems/PATULJCI/ http://www.spoj.com/problems/DISUBSTR/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ http://www.codechef.com/problems/QTREE http://www.codechef.com/problems/LEBOBBLE http://www.codechef.com/problems/DGCD http://www.codechef.com/problems/QUERY http://codeforces.com/problemset/problem/280/D http://codeforces.com/problemset/problem/117/E http://codeforces.com/problemset/problem/167/D http://codeforces.com/problemset/problem/266/E http://codeforces.com/problemset/problem/145/E http://codeforces.com/problemset/problem/226/E http://codeforces.com/problemset/problem/311/C http://codeforces.com/problemset/problem/276/E http://codeforces.com/problemset/problem/221/D http://codeforces.com/problemset/problem/174/C http://codeforces.com/problemset/problem/301/D http://codeforces.com/problemset/problem/61/E http://codeforces.com/problemset/problem/103/D http://codeforces.com/problemset/problem/165/D http://codeforces.com/problemset/problem/52/C http://codeforces.com/problemset/problem/85/D http://codeforces.com/problemset/problem/242/E http://codeforces.com/problemset/problem/111/B http://codeforces.com/problemset/problem/220/B http://codeforces.com/problemset/problem/195/E http://codeforces.com/problemset/problem/219/E http://codeforces.com/problemset/problem/281/D http://codeforces.com/problemset/problem/121/E http://codeforces.com/problemset/problem/86/D http://codeforces.com/problemset/problem/182/C http://codeforces.com/problemset/problem/19/D http://codeforces.com/problemset/problem/258/E http://codeforces.com/problemset/problem/190/E http://codeforces.com/problemset/problem/295/E http://codeforces.com/problemset/problem/160/E http://codeforces.com/problemset/problem/163/E http://codeforces.com/problemset/problem/192/E http://codeforces.com/problemset/problem/316/E3 http://codeforces.com/problemset/problem/280/E http://codeforces.com/problemset/problem/238/D SRM 310 Floating Median http://acm.pku.edu.cn/JudgeOnline/problem?id=1986 http://acm.pku.edu.cn/JudgeOnline/problem?id=2374 http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045 http://acm.pku.edu.cn/JudgeOnline/problem?id=2763 http://www.spoj.pl/problems/QTREE2/ http://acm.uva.es/p/v109/10938.html http://acm.sgu.ru/problem.php?contest=0&problem=155 Problems from LightOj Segment Tree/Interval Tree Binary Indexed Tree Range…

comment 0

বিএফএস ইমপ্লিমেন্টেশন কোড

[code language=”C”] vector<int> adj[100]; //adj[a].push_back(b); for add an edge from a to b int visited[100]={0}; //O if not visited, 1 if visited int level[100]; void addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void bfs(int s, int n) { for(int i=0; i<n; i++) visited[i] = 0; queue<int>Q; Q.push(s); visited[s] = 1; level[s] = 0; while(!Q.empty()) { int u = Q.front(); cout << u <<" "; for(int i=0; i<adj[u].size(); i++){ if(visited[adj[u][i]]==0){ int v = adj[u][i]; level[v] = level[u]+1; visited[v] = 1; Q.push(v); } } Q.pop(); } cout<<endl; for(int i=0; i<n; i++) { printf("%d to %d distance…

comment 0

ব্যাসিক জিওমেট্রি প্রব্লেম সলভিং

প্রোগ্রামিং ল্যাঙ্গুয়েজের সিনট্যাক্স শেখার পর একজন প্রোগ্রামারের প্রধান দায়িত্ব সেই সিনট্যাক্স দিয়ে নানা সমস্যার সমাধার করা । মূলত প্রোগ্রামিং বা কম্পিউটার সায়েন্সের ফিলোসপি হলো – প্রব্লেম সলভিং । আমাদের চারপাশে নানান রকম সমস্যাকে কম্পিউটারের মাধ্যমে বা সফটওয়্যারের সল্যুশন দিতে পারাটাই একজন প্রোগ্রামারের মূল কাজ । সিনট্যাক্স বা প্রোগ্রামিং ল্যাঙ্গুয়েজ এক্ষেত্রে খুব একটা গুরুত্বপূর্ণ ভুমিকা পালন করে না । ইম্পর্ট্যান্ট টার্ম হলো – ইমপ্লিমেন্টেশন । তোমার চিন্তাভাবনাগুলোকে (যেগুলো আসলে নানান সমস্যার সমাধান) সেগুলোকে কোডিং করে ইমপ্লিমেন্ট করতে পারাটাই প্রোগ্রামার হিসেবে তোমার বাহাদুরগিরি প্রকাশ করে । কপি-পেস্টিং কনসেপ্টে তুমি অনেক কিছুই তৈরী করতে পারে, কিন্তু এতে তোমার মৌলিকতা প্রকাশ পায় না ।

comment 0

প্রবলেম সলভিং – এলসিএম (১)

টপিকঃ LCM

প্রোগ্রামিং প্রবলেম সলভিংয়ে এলসিএম বেশ কমন। সাধারণত দুটি সংখ্যা দেয়া থাকে এবং এদের এলসিএম বের করতে হয়। এখানে যে প্রবলেমটি নিয়ে আলোচনা করা হয়েছে, এতে দুটি সংখ্যার ল.সা.গু(LCM) এবং সংখ্যা দুটির যেকোন একটি দেয়া আছে, অপর সংখ্যাটি বের করতে হবে।

প্রথমে কিভাবে দুটি সংখ্যার এলসিএম নির্ণয় করতে হয় দেখা যাক-

(এলসিএম নির্ণয় করার জন্য একেকজন একেক নিয়ম অনুসরণ করে থাকে। আমরা নিচের নিয়মে করবো কারণ এতে গ.সা.গু নির্ণয় করাও শিখে ফেলা যাবে।)