16321's Contest Diary

In this problem, task is to find out the largest prime number in a given range. Statement says Q (1 ≤ Q ≤ 10 ^5 ), the number of queries that will be given. The next Q lines will contain two integers l i (1 ≤ l i ) and r i (r i ≤ 10000). So for solving this, I used a sieve algorithm for storing all the prime numbers is an array from 1 to 10000. Then I apply binary search for each query.

This problem is a interactive problem. It is classical binary search interactive problem. But also got one wrong answer because left started from 0 but i put 1 . ;)

Tag of this problem is binary search. Binary search problems seems very interesting to me.  Without thinking much about the problem I submitted a simple binary search algorithm. But got wrong answer 5 or 6 times. But after carefully reading the statement I understood I have to make change to my binary search algorithm. Modified Binary Search:: int count=0;     ll mid=-1;     while(l<h)     {         mid=(l+h)/2;         count++;         //cout<<l<<" "<<h<<" "<<mid<<endl;         if(x==mid)         {             h=mid;             continue;         }      ...

First time reading the problem i thought it is easy problem.  But soon found it is not an easy problem. Statement Says:Each test case contains an integer N (1 ≤ N ≤ 10^5), denoting how many numbers to compute. And below that an array A (1 ≤ A i ≤ 100) consisting of N numbers will be given. In naive approach all the numbers are multiplied then find it is perfect square or not. That will cause a memory overflow. After trying some time, I found that only perfect square has the property that every prime factor appeared even number time in factorization. Example:: 16=2*2*2*, 25=5*5, 225=5*5*3*3. So i factored each Ai and store the counter of the factor in map. Then finally count if a factor is present with odd count. If there was any odd count then answer false. Or else answer is Yes. Indeed it is a quite nice problem.

In this blog I will write about my future problem solving, algorithm studying and contests.