Re: BdOI 2010 problemset
Posted: Tue Dec 28, 2010 6:44 pm
আমি কিন্তু round trip এ যে সমাধানের কথা ভাবছি সেটা কিন্তু brute force না কিন্তু ওটার complexity 10^8 হয়ে যায় ওই লিমিটে।number of edges*number of nodes আরকি।যাই হোক কোড কইর তোমারটা,গ্রাফের সমস্যা তো কোড করাই মজা আর সহজ।
তুমিতো stone বেশ ভালই করছিলা।এটা O(n^2) করাতো সহজ DP.কিন্তু O(nlogn) এ কিভাবে করবা??তুমি কি longest increasing subsequence O(nlogn) এ করতে পার??এই সমস্যাটা যাদিও তা না,তাও এইখানে বললাম।মিল মিল আছে।এই হচ্ছে লিঙ্ক যেখানে longest increasing subsequence O(nlogn) এ করা আছে।
http://www.algorithmist.com/index.php/L ... quence.cpp
তুমিতো stone বেশ ভালই করছিলা।এটা O(n^2) করাতো সহজ DP.কিন্তু O(nlogn) এ কিভাবে করবা??তুমি কি longest increasing subsequence O(nlogn) এ করতে পার??এই সমস্যাটা যাদিও তা না,তাও এইখানে বললাম।মিল মিল আছে।এই হচ্ছে লিঙ্ক যেখানে longest increasing subsequence O(nlogn) এ করা আছে।
http://www.algorithmist.com/index.php/L ... quence.cpp