এই জিনিসটা নিয়ে লিখার ইচ্ছা অনেক দিনের । কিছু তেমন জানি না বলে সাহস করে লিখা হয় নাই । লাইট ওজিতে অনেক ইউনিক আইডি এর অনেক ভাল প্রবলেম আছে । স্বাভাবিক ভাবে আইডিটা জানা না থাকার কারণে অনেক প্রবলেম সল্ভ হয় না । ইচ্ছা আছে এই প্রবলেমগুলার সল্যুশন ট্যাকনিক নিয়ে লিখার । এই পোস্টে লাইট ওজির ডিপি প্রবলেম গুলাকে আরো একটু ক্যাটেগরাইজ করে রাখার ইচ্ছা আছে । সামনের সিরিজগুলাতে সল্ভ ট্যাকনিক নিয়ে লিখা হবে ( যদি কোন ভাবে লিখার মোটিভেশন পাই :p )
বিশেষ কিছু ডিপি ট্যাকনিক আছে , যেমন ( LCS , LIS , MCM , Digit DP , 0/1 knapsack , Bit Mask , min vertex, Expected Value , N Queen type এমন ) . এইখানে প্রবলেম আইডি ধরে এমন ক্যাটেগরিতে ফেলার চেস্টা করছি । যেহেতু অনেক প্রবলেম এই আমার সল্ভ নাই এখনও এমন অনেক কিছু নিয়েই জানি না সব প্রবলেম করা সম্ভব হচ্ছে না । লিস্টটা আমি যথা সম্ভব আপডেট করতে থাকব । কোন প্রবলেম এর ক্যাটেগরি ভুল থাকলে বা নতুন প্রবলেম এর ক্যাটেগরি সম্পর্কে কমেন্ট এ বলতে পারেন ।
Bit Mask :::
1011 , 1018 , 1021 , 1037 , 1057 , 1061 ( + N Queen ) , 1073 ( + KMP ) , 1086 ( +Euler trail ) . 1092 , 1119 , 1158 , 1228 , 1264 ( sub set mask ) , 1270 , 1287 ( + Expected value ) , 1316 ( + Dijkstra ) , 1327 , 1406 ( subset mask ) ,
Binary Search :::
1170 , 1180 , 1360 ,
Coin Change :::
1079 , 1147 , 1226 , 1231 , 1232 , 1233 ,
Counting :::
1095 , 1140 , 1170 ( + Binary search ) , 1302 , 1326 , 1329 , 1382
Digit DP :::
1032 , 1068 , 1140 , 1205 , 1394 ,
Edit Distance :::
1013 ( + LCS ) , 1025 , 1033 , 1051 , 1159 ( can be solved by suffix array ) , 1351 , 1420
Expected Value :::
1027 , 1030 , 1038 , 1287 ( + Bit Mask ) , 1364 ,
0/1 Knapsack :::
1017 , 1106 , 1125 , 1169 , 1200 , 1217 ,
KMP :::
1073 ( + Bit Mask ) , 1334 ,
LCS :::
1013 ( + Edit distance ) , 1110 , 1157 ,
LIS ::
1277 , 1421 .
MCM :::
1031 , 1044 , 1283 , 1302 , 1422
Min vertex Cover :::
1201 , 1230 ,
Non Classical ::: 1004 , 1036 , 1047 , 1060 , 1071 , 1084 , 1105 , 1122 ,1134 , 1173 , 1191 , 1295 , 1345 ,
N Queen :::
1005 , 1061 ( + Bit Mask ) ,
Probability :::
1050 , 1064 ,
Space Reduction :::
1126 , 1145
Subset Mask :::
1264 , 1406
DP on Tree ::
1257 , 1382
Dp with BIT :::
1415
Believe it or not, I was craving for it for about two years! Great JOB.
ReplyDeleteThanks for the comment , keep visiting :)
ReplyDeleteভাইয়া , light oj 1257 প্রব্লেম টা কিভাবে শলভ করব । প্রতিটা নোডে dfs চালালে তো TLE ...
ReplyDeleteআসলে ৩টা dfs চালাতে হয় । tree diameter লিখে google search করলেই অনেক algorithm পাওয়া যায় । একটু চিন্তা করলেই ধরে ফেলতে পারবেন ।
DeleteThat is so much helpful who started to solve DP.
ReplyDeleteBhai how to solve lightoj 1005 using nqueens?Please help.
ReplyDelete