### Sumanto's blog

By Sumanto, 6 months ago,

Do deque in stl consume more memory than vector?

Memory Limit Exceeded due to Deque
Accepted when used Vector

Anyone give your insights regarding this issue? Do i missing something related to implementation of deque or vector?

• -2

By Sumanto, history, 7 months ago,

• -8

By Sumanto, 7 months ago,

You are given N red candies and M blue candies.

Write a program to find the number of arrangements of candies in which not more than K candies of the same color are placed next to each other. Answer is large so use 1e9+7;

1<=T<=10 1<=N,M,K<=1000input Format: T N M KSample Input: 1 1 1 1 2 1 1Sample Output: 2 1Explainations: 1-> RB, BR 2-> RBR 

• +6

By Sumanto, history, 8 months ago,

I searched on internet regarding this but didn't able to find perfect answer which could explain conceptually the difference between these two. Any light on this will help us all, i am sure many of would not know the theoretical difference between the two.

• -9

By Sumanto, 9 months ago,

• 0

By Sumanto, 9 months ago,

• -2

By Sumanto, 9 months ago,

• 0

By Sumanto, history, 9 months ago,

• +2

By Sumanto, history, 10 months ago,

There are two strings, s and t.

Perform two operations with string s:

1. Working from Left-to-Right delete each occurance of t in s until there are no more occurances of t. Count each deletion.
2. Working from Right-to-Left delete each occurance of t in s until there are no more occurances of t. Count each deletion.

Return Greater of the two counts.

Example: s="bcbbc" t="b" — From left To Right: s reduces to bcbbc->cbbc->cbc->cc, The number of moves is three — From Right To Left: bcbbc->bcbc->bcc->cc , The number of moves is three So ans is max(L-to-R,R-to-L)=3;

Example: s="aabb" t="ab" — From left To Right: s reduces to aabb->ab->"", The number of moves is two — From Right To Left: s reduces to aabb->ab->"", The number of moves is two So ans is max(L-to-R,R-to-L)=2;

Constraints: 1<=length(s)<=2*10^4 1<=length(t)<=100

snaps of the problem: https://imgur.com/a/uvOgvbh

• -19

By Sumanto, 10 months ago,

• 0

By Sumanto, 10 months ago,

• +5

By Sumanto, 10 months ago,

A coach of a school chess club wants to start a mentoring program for newer players. Each player has an integer rating representing skill level. The coach would like to pair up students whose ratings differ by no less than a given minimum. What is the maximum number of pairs that can be formed?

for ex: n=6; rating=[1,2,3,4,5,6]; minDiff=4; ans: 2; explaination: There are Two pairs of players have a difference of 4 or more; those ratinggs are (1,5) and (2,6)

Constraints: 1<=n<=2*10^5 0<=rating[i]<=10^9 0<=minDiff<=10^9

This was asked in Hackerank intermediate certification Test.I failed to come up with a solution better than quadratic.

• -23

By Sumanto, 10 months ago,

given an array of non-negative integers, count the number of unordered pairs of array elements such that their bitwise AND(&) is a power of 2. 
for ex: for array [10,7,2,8,3]; there are 6 unordered pairs; explaination: 10&7=2 10&2=2; 10&8=2; 10&3=2; 7&2=2; 2&3=2; 
Constraints: 1<=n<=2*10^5 0<=ar[i]<=2^12 
This was asked in Hackerank intermediate certification Test.I failed to come up with linear time solution. 

• +8

By Sumanto, 10 months ago,

I implemented my solution using LIS(nlogn way) in this Problem F: LIS on Tree. Issue is I'm Facing that,by changing the position changing the snippet code where LIS is getting calculated is giving me correct answer but giving TLE(time limit exceeded) in other way. As far as i can see this does not change the time complexity any how. Am I missing something conceptually on knowledge of LIS or on DFS?

TLE When LIS calculation inside for loop

**CODE SNIPPET:** void dfs(int i,int parent,set<int>& seq,vector<int> &ar,vector<int> &ans) {  set<int> temp=seq;  for(auto j:edges[i])  {  if(j!=parent)  {  seq=temp;  if(seq.lower_bound(ar[j])!=seq.end())  {  //auto p1=*seq.lower_bound(ar[j]);  seq.erase(seq.lower_bound(ar[j]));  seq.insert(ar[j]);  ans[j]=max(ans[j],(int)seq.size());  dfs(j,i,seq,ar,ans);  // seq.erase(ar[j]);  // seq.insert(p1);  }  else  {  seq.insert(ar[j]);  ans[j]=max(ans[j],(int)seq.size());  dfs(j,i,seq,ar,ans);  //seq.erase(ar[j]);  }  // for(auto p:seq)  // cout<<p<<" ";  // cout<<"\n";
}
}} 
Accepted after changing LIS snippet outside for loop

**CODE SNIPPET:** void dfs(int i, int parent, set<int>& seq, vector<int> &ar, vector<int> &ans) {  int temp=-1;  if (seq.lower_bound(ar[i]) != seq.end())  {  temp=*seq.lower_bound(ar[i]);  seq.erase(seq.lower_bound(ar[i]));  seq.insert(ar[i]);  }  else  seq.insert(ar[i]);  ans[i] = max(ans[i], (int)seq.size());  for (auto j : edges[i])  {  if (j != parent)  {  dfs(j, i, seq, ar, ans);  }  }  seq.erase(ar[i]);  if(temp!=-1)  seq.insert(temp); } 

• 0

By Sumanto, 12 months ago,

I implemented my solution using Binary Search in this Problem A: Deadline. Issue is I'm Facing that,by changing the value of high from 1e18 to n-1, my solution which was giving wrong answer now being accepted. To be on the safe side, I kept high=1e18, but it's giving wrong answer. Any Help on this would be really appreaciated. Am I missing something conceptually on knowledge of Binary Search?

Accepted after high=n-1

• 0

By Sumanto, history, 14 months ago,

` My question : How to approach and solve this problem? I feel like there are many ways to approach this problems but did'nt had time left to solve this.