একটি গুরুত্বপূর্ন অ্যারের পার্টিশন এ আমরা একটি unique non-decreasing sequence বের করতে পারি। সেটা হল প্রতি সাবঅ্যারে থেকে আমরা greedily next smallest একটি করে উপাদান নিব। যেমন ${[2, 2, 3], [2, 3, 4], [1, 3, 4]}$ থেকে আমরা greedily $2, 2, 3$ অনুক্রুম টি নিব। তো আমরা কাউন্ট করব এই unique sequence গুল থেকে।

কাউন্ট করার জন্য আমরা ডাইনামিক প্রোগ্রামিং অবলম্বন করবো, ধরি $dp[pos][num] =$ প্রথম pos টি উপাদান ব্যবহার করে কতগুলো গুরুত্বপূর্ণ পার্টিশন করা যায় যেখানে sequence টির শেষ উপাদান হল num। যেমন $[3, 1, 2, 4]$$dp[4][4] = 3$, তা হল ${[3, 1, 2], [4]}, {[3, 1], [2], [4]}, {[3], [1, 2, 4]}$ এই $3$টি।

তো প্রথমেই একটি $n^4$ সলিউশন লেখা যায় যেখানে $dp[num][pos]$ বের করতে আমরা $pos$ থেকে কিছুটা পিছাবো, $pos'$ এর আগ পর্যন্ত। তারপর এমন সকল $dp[num'][pos']$ এর যোগফল নিব যেন $dp[num'][pos']$ এর একটি sequence এর শেষ উপাদান $num'$ এর পর $[pos'+1.....pos]$ সাবঅ্যারে থেকে next smallest উপাদান num হয়। এক্ষেত্রে খেয়াল রাখতে হবে যেন, $[pos'+1...pos]$ এর ভিতরে $num'$ এর চেয়ে সমান বা বড় উপাদান $num$ ই হয়।

এই সলিউশন টিকে $n^3$ বানানো যায় যদি খেয়াল করো যে একটা নির্দিষ্ট $pos'$ এ আসলে আমরা $num'$ এর একটি রেঞ্জ পাই, তা হল, $[x+1, num]$, যেখানে $x$ হল $[pos'+1...pos]$ এর ভিতরে $num$ থেকে ছোট সবচেয়ে বড় সংখ্যা । অর্থাৎ ওই রেঞ্জে থাকা সব $num'$ এর জন্যই $dp[num'][pos']$ , $dp[num][pos]$ এর সাথে যোগ হবে। যেহেতু এই রেঞ্জ এর সংখ্যা গুলো আগেই কম্পিউট করা হয়ে গেছে, তাই আমরা cumulative sum এর অ্যারের সাহায্যে $O(1)$ টাইম এ রেঞ্জ সামটি পেতে পারি। আবার একটি জিনিস খেয়াল রাখতে হবে, তা হল আমাদের $pos'$ যাতে এমন হয় যেন $[pos'+1...pos]$ এ কমপক্ষে একটি $num$ থাকে।

এই সলিউশন টিকে $n^2$ বানাতে হলে আরো অবজার্ভ করতে হবে যে $dp[pos][num]$ বের করতে গিয়ে আসলে আমরা যে সকল $dp[pos'][num']$ যোগ করি তারা আসলে শুধু একটি রেঞ্জই না বরং কিছুটা rectangle range এর মত। এক্ষেত্রে ভাল হবে যদি তোমরা হাতে কলমে একটি 2d dp table বানিয়ে দেখ যে $dp[pos][num]$ এ কারা কন্ট্রিবিউট করে। তো আমরা যেটা করব তা হল বের করব আগে এমন $p$ যার জন্য $[p+1...pos]$ এ শুধু মাত্র $p+1$ অবস্থানেই $num$ আছে ($p$ এর চেয়ে বড় $pos'$ গুলো কিন্তু কোন কন্ট্রিবিউট রাখতে পারবে না । এরপর প্রথমেই আমরা সব $dp[pos'][num]$ যোগ করে দিব যেন $pos' <= p$ এবং $num' <= num$, এটি 2d cumulative sum এর সাহায্যে $O(1)$ এ করা যাবে। এতে কিছু ওভার কাউন্ট হয়েছে, যে যে $pos', num'$ এর জন্য $pos' \leq pos'' \leq pos$ এবং $num' \leq num'' \leq num$ আছে যেন $A[pos''] = num''$। তো আমরা যেটা করব, একটি $pos$ নির্দিষ্ট করে যখন $num = 1...n$ এর জন্য $dp[pos][num]$ বের করব তখন একটি stack মেইন্টেইন করতে করতে যাব যার ভেতরে $num'', pos''$ গুলো থাকবে, decreasing order এ, এই stack টি আপডেট করার সময়ই আমরা ওভারকাউন্ট করা অংশ গুলি বিয়োগ করে দিব (সেটাও 2d cumulative sum এর মাধ্যমে)। এতে সলিউশনটি $n^2$ হবে।

Statistics

50% Solution Ratio
NirjhorEarliest, Jun '20
Yasir_ArafatFastest, 0.8s
nusuBotLightest, 99 MB
Yasir_ArafatShortest, 943B
Toph uses cookies. By continuing you agree to our Cookie Policy.