Tuesday, June 13, 2017

[Tutorial] Toph - Is It A Square (solution)

Problem Description:


$N$ সাইজ বিশিষ্ট অ্যারে $A$ দেয়া আছে । এরপরে Q সংখ্যক কুয়েরি আছে । প্রতি কুয়েরিতে দুইটি সংখ্যা দেয়া আছে $l$ ও $r$ । 
বলতে হবে, অ্যারের $l$ থেকে $r$ পর্যন্ত সব সংখ্যা গুলিকে গুণ করলে গুণফল পুর্ণ বর্গ হবে কি না । 

Constraints:


$1 \space \leq N \space \leq \space 10^5$
$1 \space \leq Q \space \leq \space 10^5$
$-10^5 \space \leq A[i] \space \leq \space 10^5$


Problem Link: Is it A Square


Solution:


Prerequisite:

সলিউশনের জন্য আগে থেকেই যা যা জানা থাকতে হবে - 
  1.  Cumulative Sum or Prefix Sum, or Cumulative Frequency Counting
  2. Sieve of Eratosthenes
  3. Prime Factorization
  4. MO's Algorithm
যেহেতু $10^5$ টা সংখ্যাকে গুণ করলে তা স্টোর করা সম্ভব না, অতএব আমাদের Square Number এর অন্য কোন প্রোপার্টিজ ব্যবহার করতে হবে ।

একটি সংখ্যা পূর্ণ বর্গ হলে, তার প্রতিটা প্রাইম ডিভিজর জোড় সংখ্যক বার থাকে । যেমন, ৯ = ৩ * ৩,
৪ = ২*২*২*২, ২৫ = ৫*৫, ৩৬ = ২*২*৩*৩ ইত্যাদি ।

অতএব, আমরা অ্যারে এর প্রতিটা সংখ্যাকে প্রাইম ফ্যাক্টোরাইজেশন করে নেব । এরপরে দেখব, $l$ থেকে $r$ পর্যন্ত অ্যারের সংখ্যাগুলোকে গুণ করলে তাদের গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা ।

গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা, সেটা আমরা MO's Algorithm ব্যবহার করে বের করব ।

odd নামের একটা global ভ্যারিয়েবল নেব, যার ভিতর থাকবে এখন পর্যন্ত মোট কয়টা প্রাইম ডিভিজর বিজোড় সংখ্যক বার আছে । 

MO's Algorithm এর প্রতি ধাপে যখন কোন ইন্ডেক্সে যাব, তখন সেই ইন্ডেক্সের সংখ্যাটির প্রতিটা প্রাইম ডিভিসর count এর মান 1 বাড়াবো (add এর ক্ষেত্রে ), অথবা 1 কমাবো (remove এর ক্ষেত্রে ) । প্রতিবার বাড়ানো বা কমানোর সময় চেক করব, ঐ প্রাইম ডিভিজর এর count এর বর্তমান মান এখন বিজোড় কিনা । যদি বিজোড় হয়, তবে odd এর মান এক বাড়াবো, বিজোড় না হলে odd এর মান এক কমাবো । ফুল রেঞ্জ iterate করার পরে যদি odd এর মান 0 হয় ( odd এর মান 0 মানে হলো, এখন পর্যন্ত বিজোড় সংখ্যক বার আছে এমন প্রাইম ডিভিজর এর পরিমাণ 0), তবে গুণফল Square নাম্বার হবে, নতুবা হবে না । 

তবে দুইটি কর্ণার কেস আছে :

  1. যদি রেঞ্জের ভিতর এক বা একাধিক 0 থাকে, তবে গুণফল Square Number হবে । 
  2. যদি রেঞ্জের ভিতরে বিজোড় সংখ্যক negative number থাকে, তবে গুণফল Negative Number হবে । অতএব এক্ষেত্রে গুণফল Square Number হবে না । 
তবে এই দুইটা কন্ডিশন আমরা Cumulative Sum এর সাহায্যে O(1) এই চেক করতে পারব ।


এই সলিউশনের complexity হবে $O((N+Q) . sqrt(N) . log n)$


Code:



6 comments:

  1. মনে ব্যাথা পাইলাম :(
    Mo পারিনা

    ReplyDelete
    Replies
    1. লিংকটা থেকে শিখে ফেলেন । কাজের জিনিস খুব এটা ।

      Delete
  2. Tutorial একটু Clean কোড দিতেন :(

    ReplyDelete
    Replies
    1. টেমপ্লেট সরানোর কথা বলছেন ?

      Delete
    2. code কিছুটা এডিট করে দিলাম ।

      Delete