Light Oj 1100 ( Again Array Queries )

আজকে সকাল বেলায়ই আমি এই প্রবলেমটা পড়তেছিলাম  এইখানে আমাকে nটা নাম্বার ইনপুট দেওয়া হইছে আমাকে তারপর বিভিন্ন query দেওয়া হবে আমাকে বলতে হবে এই query এর মধ্যে minimum difference এর ভ্যালু কোনটি নাম্বারগুলার মধ্যে । প্রবলেমটা পড়ার সাথে সাথে আমার মাথায় যেই আইডিয়াটা আসল এইটা হল এইটা তো segment tree এর প্রবলেম আমি জাস্ট রেঞ্জ এর মধ্যে বেস্ট মিন ভ্যালু আর সেকেন্ড বেস্ট মিন ভ্যালু শেভ করে রাখব তাদের ডিফারেন্স এই আমার আন্সার । আবারও সেম ভুল কোন আইডিয়া আসা মাত্রই কোড করতে বসা ( হাসিব বলে যাই মাথায় আসুক আগে একটা প্রুফ করবা এইডা কাজ করবে কিনা তারপর কোড ) এবং কোড করে সাবমিট "Wrong Ans" . যেহেতু প্রতিটা ভুল চিন্তার পিছনে একটা বিশ্বাস থাকে এইটা সঠিকই ছিল ফোরাম এ কোন স্যাম্পল ইনপুট/আউটপুট আছে কিনা চেক করতে গেলাম , সাথে সাথে গিয়েই দেখি ফাইয়াজ ভাই একটা ভাল টেস্ট কেস দিয়ে রাখছে যেইটা শুধুমাত্র প্রমাণ করে না আমার কোড এ ভুল আছে সাথে সাথে এইটাও আমার আইডিয়াটা আসলে বস্তা পচা ছিল ।

কেসটা ছিল
1
6 1
10 2 7 8 13 16
0 5

আমার লজিক এ আন্সার আসা উচিত সেকেন্ড বেস্ট মাইনাস বেস্ট মিন এইখানে ৭ - ২ = ৫ কিন্ত্ আসলে ৮ - ৭ , আসলে বেস্ট আর সেকেন্ড বেস্ট মিন এর ডিফারেন্স এই যে উত্তর হবে এইটা কখনই ঠিক না , বেস্ট , সেকেন্ড বেস্ট এর ডিফারেন্স ও হইতে পারে । কিভাবে সল্ভ করা যাইতে পারি যখন ভাবতেছি তখন একটা সবচেয়ে Interesting ব্যাপার খেয়াল করলাম । এইখানে Rang [1-1000] আর n <= 10^5 আমি যদি frequency এর কথা চিন্তা করি তাহলেও কিন্তূ টাইম লিমিট এর মধ্যে হয় । এইখানে worst case এ প্রতিটা query এর জন্য ( query লিমিট 10^4) 10^4 * 10^ 3 == 10^7 loop চলবে । query এর রেঞ্জগুলা sort করে আমি অনেক extra overlapping কাজ ও দূর করতে পারি । আসলে মেইন আইডিয়া হল আমি রেঞ্জ এর ভ্যালু গুলা চেক করব কোন রিপিট থাকবে তো সাথে সাথেই  0 . যদি তা না থাকে তাহলে এদের মধ্য থেকে আমি আমি পর পর সবচেয়ে কম difference এর ভ্যালু বের করব ।

one code is better than any discussion
const int MX = (1e5+10);
int inp[MX] , freq[1005];
int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0);
    int cs , t , n , x , y , q , j, i ;
    read(t);
    for ( cs = 1 ; cs <= t ; cs++ )
    {
         scanf("%d %d",&n,&q);
         rep(i,n)
         {
             scanf("%d",&inp[i]);
         }
         printf("Case %d:\n",cs);
         for( i = 0 ; i < q ; i++ )
         {
             scanf("%d %d",&x,&y);
             memo(freq,0);
             bool rep = 0 ; // kono number repeat ase kina
             int ans = (1e+5);
             int prev = -1;
             for ( j = x ; j <= y ; j++ )
             {
                   if(freq[inp[j]]) // repeat hoiche value
                   {
                       rep = 1 ;
                       break;
                   }
                   freq[inp[j]] = 1 ;
             }
             if(rep)
             {
                 printf("0\n");
                 continue;
             }
             for ( j = 1 ; j <= 1000 ; j++ )
             {
                 if(freq[j])
                 {
                     if(prev == -1 )
                     prev = j ;
                     else
                     {
                         ans = min(ans,j-prev);
                         prev = j ;
                     }
                 }
             }
             printf("%d\n",ans);
         }
    }

    return 0;
}

রেঞ্জ [1-1000] এর মধ্যে থাকার কারনে এইভাবে তো করা গেল , কিন্ত্য যদি রেঞ্জ [1-10^5/10^6] হইত তাহলে segment tree তে বা অন্যকোন ভাবে কিভাবে সল্ভ করা যাইত আমি জানি না । কিভাবে হইতে পারে রেঞ্জ বড় হইলে কারো আইডিয়া থাকলে অবশ্যই কমেন্ট এ বলবেন।

-- Shakil Ahmed

Welcome Everyone

On behalf of AUST ACM Programming Community i would like to welcome you  to our community blog where we would like to share our knowledge , mistake we done in contest , story about our contest  . Stay tune lots of  competitive programming discussion are coming .

-- Shakil Ahmed