Sumanto's blog

By Sumanto, 6 months ago, In English

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?

Read more »

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

By Sumanto, history, 7 months ago, In English

My earlier code which was giving error: complete implementation here: https://ideone.com/MuOmlS

Code giving compilation error

This Code giving error as:

ERRORS

correct code after referring this thread https://stackoverflow.com/questions/12466055/field-has-incomplete-type-error/12466219 i implemented and it worked but from this thread i couldn't able to understand why pointer object is doing which leads to removal of error?

complete implementation here: https://ideone.com/SSVnOU

Correct code ( doubt is don't know why working correctly)

UPDATE:

After referring some blogs i came to know there is also an another way of handling this case

Different implemetation (correct)

I Believe i am missing some concept of c++ language which i need to know to understand what's going on here. Please share your views regarding this.

Read more »

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

By Sumanto, 7 months ago, In English

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<=1000

input Format: T N M K

Sample Input: 1 1 1 1 2 1 1

Sample Output: 2 1

Explainations: 1-> RB, BR 2-> RBR

NOTE: https://ideone.com/A1Cldk i used this way but it lead to Memory Limit Exceeded as expected.

Read more »

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

By Sumanto, history, 8 months ago, In English

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.

Read more »

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

By Sumanto, 9 months ago, In English

https://www.hackerrank.com/contests/pasc-dp/challenges/contiguous-maximization My approach to this problem was to calculate maximum sum of each length sub-array's of each row separately and then use the length as weight and sum as price make it work like the way knapsack works. But issue is that i'am facing wrong answers in large test cases and not able to figure out why am i getting WRONG ANSWER. Any help would be really helpful

My submission

Read more »

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

By Sumanto, 9 months ago, In English

https://cses.fi/problemset/task/1195 to solve this problem i implemented dijkstra's and Dynamic Programming to decide whether to opt for coupon or not for each state transiton.But I'am getting TLE and not able to optimize my code. I think my approach is slow. Any suggestion please help. Here is william lin's code https://youtu.be/dZ_6MS14Mg4?t=13603 but i did't get his approach. If any one could explain what he did will be helpful

My Code

Read more »

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

By Sumanto, 9 months ago, In English
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sumanto, history, 9 months ago, In English
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By Sumanto, history, 10 months ago, In English

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

Read more »

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

By Sumanto, 10 months ago, In English
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sumanto, 10 months ago, In English
 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By Sumanto, 10 months ago, In English

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.

Read more »

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

By Sumanto, 10 months ago, In English

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. 

Read more »

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

By Sumanto, 10 months ago, In English

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 LINK:

**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 LINK:

**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); } 

Read more »

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

By Sumanto, 12 months ago, In English

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?

Wrong Answer due to high=1e18
Accepted after high=n-1

Read more »

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

By Sumanto, history, 14 months ago, In English

  ` 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.

Read more »

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