aop's blog

By aop, history, 8 days ago, In English

Hello, freinds recently i was confronted with a problem which goes like this->

Given a positive odd prime number p and another positive integer k (1<k<=p-1) find the minimum value of m such that pow(k,m)%p=1.

One straight way of approaching this is to iterate untill we get what we need thus contributing a time complexity of O(p), but i fancy if there exists even a more efficient way to do so. Can anyone help me or give some clue of how to solve it in less than O(p) time complexity.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 2 months ago, In English

Hello everybody! Recently i was solving the problem Voting (Hard Version) on codeforces. But, after reading the problem I had a doubt-:

Can a voter vote if the number of other voters already voted is greater than mi or is it necessary to have exactly mi voters for this voter to get convinced for voting.

For example — If we have the mi array as [1,1,2,3,4,4,4,5,5] and the price array as [1,2,2,2,2,2,2,2,2]. Then how will the voting take place in an optimal way. Can it take place like (1)->(1,1)->(1,1,2)->(1,1,2,3)->(1,1,2,3,4,4,4)->(1,1,2,3,4,4,4,5,5) wiht a net cost of 1?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 2 months ago, In English

Hello, everybody! Recently i was solving a problem League on atcoder.

I submitted a solution which according to me is O(N*N*N) and so under the given constraints (N<=1000) should not pass, but since it got accepted ,it suggests the time complexity to be O(N*N). Can someone help me finding its right time complexity.

My Code

My Idea:- We initially maintain an array of pointers ptr[] of n teams each pointing to the very first index in its row i.e setting ptr[i]=1 (in 1 based indexing) for all i from 1 to n. Then untill and unless we could not find any valid match we continue our search (searching two positions i and j such that a[i][ptr[i]]==j and a[j][ptr[j]]==i and mark all such two positions and increment ptr[i] and ptr[j] i.e ptr[i]++ and ptr[j]++ for every such pair of indices) and so in each iteration of the main while loop we increase day by one (initially day=0.)

At last we check if any of the pointer ptr[i]<n which indicates we are short of some matches then our ans is 0 else ans=day.

Why it's time complexity should be O(n*n*n)-: The total number of the outermost iteration can be n*n in the worst and in such iteration we are doing linear search through the array of pointers , so it total time complexity should be O(n*n*n). But surprisingly, it seems to be O(n*n). Can someone explain me why is it so?

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Hello,friends. Recently, I was solving a problem Two Platformswhich required sorting the pairs in such a way that the elements with the smaller value of second element is sorted earlier and if the the second element of two pairs are same then the element with smaller value of first element is sorted earlier, I just want to ask what should be our comparator for this.

Wrong Answer with first compartor

Right Answer with comparator of second type

Should it be like:

bool comp(pair<ll,ll>a,pair<ll,ll>b) { return a.second<b.second; }

or

bool comp(pair<ll,ll>a,pair<ll,ll>b) { if(a.second==b.second) return a.first<b.first;

return a.second<b.second; }

Well, when i tried submitting my code with the first comparator and it gave me the wrong result but with the second one everything worked fine.Can someone explain his idea about this.

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Hello friends, while solving the problem "stonned game" asked in codeforces round #666 div 2. i submitted a solution which according to me should not get accepted but is getting accepted . I couldn't still get how is it working?The only modification i did is not updating a[id] after every recursive call. Can you help me? Should be accepted, but is not actually

Shoud not accepted but is getting accepted actually

Read more »

 
 
 
 
  • Vote: I like it
  • -24
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Can anyone share his approach or idea of solving this beautiful problem. I couldn't get any way to solve this.The tutorial given , is in japanese. I used the google translate and whatever little i got to know is that we only need to check if it is possible to reach the bottom rightmost cell of a grid of size(h*((2h-1)*w)) form (1,1).If it is, then the answer is yes,else no. Please, reply if someone can help!

Infinite Grid

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Can anyone help me figure how to get AC in this problem. I tried to solve it with binary search, made several submissions,but couldn't get AC. My idea is to search from 0 upto 1e18 and check if this number of products is possible or not and thus correspondingly increase or decrease my bounds and keep a track of maximum number of products possible and finally output it. It would be very helpful if someone could share his/her approach.

Problem SPOJ

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Can someone tell me something about him. I want to know just out of curiosity.

Read more »

 
 
 
 
  • Vote: I like it
  • +52
  • Vote: I do not like it

By aop, history, 3 months ago, In English

Can anyone explain me how to solve this problem .I read its editorial several times but still couldn't understand it. I checked it discuss section in codeforces, but nothing more has been said about this problem. Problem Editorial

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 4 months ago, In English

Can anyone explain what we should prefer "\n" or '\n' for adding a newline character or both are actually the same thing?

Read more »

 
 
 
 
  • Vote: I like it
  • -37
  • Vote: I do not like it

By aop, history, 4 months ago, In English

Hello,friends! Recently , i was solving a problem on data structures from codeforces Merge Equals. In this problem , i used a sorted list of pairs stored in a set. I wanted to get the second element just greater than or equal to a given element(a pair in this case) . For ,this i used lower_bound function to first get the required element and the incremented the iterator. But, unfortunately ,it gave me the wrong answer. But, when i just removed the element corresponding to iterator (before incrementing it) and the again used it=st.lower_bound({x,y}), it gave me the right answer. So, I want to ask why accessing a pair by incrementing iterator doesn't work in my case. If anyone can throw some light on the concerned issue, it would be highly beneficial for me and others too. Accepted Code Wrong Answer Code

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By aop, history, 4 months ago, In English

Hello,guys! I tried to solve the problem candies distribution of codeforces. But, i don't know why it is giving wrong answer on test 67. My idea is to find the highest element in each iteration (because the highest element will have no element greater then it in its left or right sides, So l[i]=r[i]=0.) and the allocate the val (initially val=n) to all such positions and subtract their contribution from every position accordingly and then do val--. Although the editorials approach is different from mine, I will be happy to know where am i wrong or my idea is not correct. This is the problem

My code

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 5 months ago, In English

I tried my lot to debug why my code for the probem "Beautiful Graph" ig giving me a TLE. I have just used dfs .PLease someone reply if one can help me out! This is the problem . This is my code!

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

By aop, history, 5 months ago, In English

Recently ,I faced a question which says that given a square matrix of size n x n with entries only as 0 ans 1's ,we are required to count the number of unique paths from (1,1) to (n,n) if "0" means that the cell is safe and "1" means that there is an obstacle. We are allowed to move in four directions if possible that is from (X,Y), one can move to (X,Y+1), (X,Y-1),(X+1,Y) or (X-1,Y). Each cell can be visited at most once. I tried to solve it with dyanamic programming , but couldn't make my way to AC. One thing more, N<=20. Can anyone give me some hint how to solve this?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By aop, history, 5 months ago, In English

Can anyone provide me a good set of dsu problems that exclusively includes its usage and can only be solved through it and not by any others like dfs or bfs!

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By aop, history, 5 months ago, In English

I have recently read tutorial on dsu on trees in codeforces (Arpa's Blog).See this blog.(Specifically,the one titled easy to code in O(nlogn))I couldn't understand how the time complexity of it is O(nlogn).Please ,someone explain me!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aop, history, 5 months ago, In English

This is the problem[This is the problem](http://Vasya and Good Sequences)Can someone explain me why it is so written in its tutorial that if the length of sequence is greater than 61 than we don't need to check the maximum condition![problem:1030E]

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By aop, history, 5 months ago, In English

I recently read the tutorial on MO's algorithm and found that the time complexity of mo's algorithm is O(q*(n/k)+n*k) where k is the block size and q is the number of queries. But ,how can it be so? For example- If i take q=2 and the ranges to be [1,n] and [n-1,n]. Then ,obviously the left pointer will have to move approx n cells and not q*sqrt(n) which is 2*sqrt(n). Please ,someone clarify my doubt!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it