code.degub's blog

By code.degub, history, 2 months ago,

Guys please share your approaches for the problems you solved. How many did you guys solve?

• +13

 » 2 months ago, # |   0 Can anyone share the problems?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +22 q1 q2 q3 q4 q5 q6
•  » » » 2 months ago, # ^ |   0 I solved first with Sliding window Maintaining a hashmap of size two for tracking Frequency and checking for additional N/3 minimum Frequency requirement ,
•  » » » » 2 months ago, # ^ |   +6 I guess it can be solved by simply checking all substrings of size 3.
•  » » » » » 2 months ago, # ^ |   0 Yes even i did this one in question DP Integers some test cases were changed after sometime
•  » » » » 2 months ago, # ^ |   0 It can be solved by checking every substring of length 3 only also, no need to use sliding window.Now, question arises why only length 3 , it can be more than that , right?So, here is the answer .... Spoilersuppose if length is greater than 3 then also one can verify that it will contains a golden string of length 3 in it. Try dry running the algorithm.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 what about abca , you have to check substring of size 5.means if there exists two indices(i,j) such that s[i]=s[j] and abs(i-j)<=4 then answer is true(if string size is greater than 3) else answer is false.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 NO. abca has 3 different characters in every window so no golden string.
•  » » » » » » » 2 months ago, # ^ |   0 oh yes i forgot this condition.
•  » » » » » » 2 months ago, # ^ |   0 There is a condition that golden string should contains exactly 2 distinct characters. So, checking only substrings of length 3 will work
•  » » » » » 2 months ago, # ^ |   +2 It could be also proved by let's say there exists a golden string of length>4 that is golden than it will surely contain {i,i+1} such that si != si+1and therfore{i-1,i+1} or {i,i+2} substring will also be golden whichever exists.
•  » » » » 2 months ago, # ^ |   0 Can you share your code?
•  » » » » 7 weeks ago, # ^ |   0 Hashmap is not needed simply take two int variables for maintaining frequency.
•  » » » 2 months ago, # ^ |   0 Can you suggest how to solve "Swap it Harder"
•  » » » 2 months ago, # ^ |   0 For 2nd question:- map mp; queue q; int n=A.size(); for(int i=0;i2) { char ch=q.front(); q.pop(); mp[ch]--; if(mp[ch]==0) mp.erase(ch); } if(mp.size()==2 && q.size()>=3) { int p=q.size(); p/=3; auto it=mp.begin(); if(it->second>p) { return 1; } it++; if(it->second>p) return 1; } } return 0; 
•  » » 2 months ago, # ^ |   0 Question no.2 was actually easier than expected. You just had to try out a few inputs first and find its output through the given tool. My solution is a bit unorthodox. The cost followed a pattern. 1. The first three conditions checked if both inputs are zero(op=0) / one of them is one(op=3). 2. Then made a while loop with the condition as min(A, B)>=(2**i). 'i' will be incremented by one every time, starting with i=1. 3. Final output will be cost=i+2
 » 2 months ago, # |   0 How to approach the problem with the rocket jumping in powers of two? I tried simulating it with bruteforce but always WA
•  » » 2 months ago, # ^ |   +5 In that you could easily compute xj array and let dp[i] be the answer for musk rocket to come at i hence the problem reduced to for each i given k disjoint intervals [l_i,r_i] and value of k would be atmost 20(actually less than that too) and if we are at i then just update all the intervals that could be done by segment tree or fenwick tree but could also be done by some ranged update in a query (like updating for [l_i,r_i] by adding dp[i] to it ->dp[l_i]+=dp[i] and dp[r_i+1]-=dp[i] then if we are at i then we no the answer available at i by just summing over values before that or just adding the initials.
•  » » » 2 months ago, # ^ |   0 Yeah thats pretty obvious and this is what I was doing but my answer was wrong from n >= 6. Maybe I had implementation issues.
•  » » » 2 months ago, # ^ |   +3 As the range update queries will always be to the right of the current index i, we can use a difference array and keep taking its prefix sum while traversing from left to right. The implementation will be much shorter and easier.
 » 2 months ago, # |   0 Can you please tell, how did you get to know about contest and where was link given?
•  » » 2 months ago, # ^ |   0 Interviewbit
 » 2 months ago, # |   0 To solve DP integers: I just applied dp with recursion: f(a, b) = min{if (a == 0 and b == 0) return 0;if (a != b) return f(sqrt(a*b), sqrt(a*b) + 2;if (a > 0) return f(a/2, b) + 1;if (b > 0) return f(a, b/2) + 1;}To solve Two summations: Used greedy: sorting. Observation: a_i + b_j dominates b_i + a_j when a_i + b_j > b_i + a_jRearrange the equation and apply sort function.a_i — b_i > a_j — b_jAfter sorting, calculate the contribution of each number, since i < j and j will dominate i.
•  » » 2 months ago, # ^ |   0 What's the time complexity of dp Integers solution? Also, I don't understand the Two Summations, can u help me with them?
•  » » » 7 weeks ago, # ^ |   0 So you are given two numbers. And to make them both zero you can either replace them with their product of square roots or divide any of them by 2. But if you observe that sqrt(a*b) >= min(a,b) so this doesn't help us to reach zero. So what I thought that first make the smaller one to zero with log(min(a,b))+1 operations (+1 to actually make to 0 from 1). So now we have {0, max(a,b)} as two numbers now the sq root of their product is 0 and it will cost '2' to make them all zero. And we have the answer. Ans= log(min(a,b)) + 1 + 2. BUT PLEASE CHECK FOR THE EDGE CASES.
•  » » 2 months ago, # ^ |   0 Could you please explain TWO summation using code?
•  » » 2 months ago, # ^ |   0 In DP Integers the test case was so weak that my code seemed to have passed just with a greedy solution i.e check if A
 » 2 months ago, # |   +11 Where I can see scoreboard or standings ?
 » 2 months ago, # |   +6 I solved 3. A lot of people whom I know solved 4 or more.
•  » » 2 months ago, # ^ |   0 How to solve 3rd or 4th one ?? (whichever you solved :_:)
 » 2 months ago, # |   0 Anybody explain "Swap it Harder".
 » 2 months ago, # |   0 Can anyone share the approach for the last problem?
•  » » 2 months ago, # ^ |   0 did you get 4th question ? I solved it in o(n*n) . Please share the approach! Thanks in advance
•  » » » 2 months ago, # ^ |   0 I also managed to solve it in O(n ^ 2) only! But someone already posted the approach can u check here for the solution
 » 2 months ago, # |   +11 My friend has received an email stating the test cases of DP integers have changed,before for 0 0,output was given as 2 and I think everyone wrote the solution accordingly,but then after the contest I came to know that it was changed,is there anyone with the same scenario ?
•  » » 2 months ago, # ^ |   0 yes, even I got 2 for 0 0 input.Can we view the questions after the contest is over in Interviewbit?I tried but it wasn't available
•  » » » 2 months ago, # ^ |   0 They later on updated the value for 0,0 to 0 ,
 » 2 months ago, # | ← Rev. 2 →   0 Solution to the first problemI am simply having a window where atmost 2 diff characters can come and then I check for conditons of golden string. Incase of it consist of more than 2 char ,I am contracting my window by incrementing left index and for expanding I am incrementing right index . int solve(string s){ int ans=0; int l=0,r=0; int n=A.size(); unordered_map< char,int>frq; frq[A[0]]++; while(l2){ frq[A[l]]--; if(frq[A[l]]==0)frq.erase(A[l]); l++; } else{ if(r-l+1>=3 && frq.size()==2){ int mini=INT_MAX; for(auto c:frq){ if(c.second>(r-l+1)/3){return true; } } } r++; frq[A[r]]++; } } return false; } 
 » 2 months ago, # |   +41 This contest was a crap. Wasted 4 hours
•  » » 2 months ago, # ^ |   0 why tho? too easy for you?
•  » » » 2 months ago, # ^ |   +19 Absolutely not. You know the test cases issue with the second problem. I still don't understand what we are supposed to do in the third problem. There was an option like see expected output for custom input, for third problem when I gave 9 9 1 as input the output was 1 but according to the sample test cases it should be 0. O(nlogn) doesn't pass for the fourth problem. I had to optimize it to O(n). For fifth problem, the problems statement is somewhat wrong.
•  » » » » 2 months ago, # ^ |   0 What approach did you follow in 4th question?
•  » » » » » 2 months ago, # ^ |   0 I don't think we can view our solutions. I initially solved the problem using maps. After I got TLE, I used arrays instead of maps. Hashed negative values to positive indices by adding -min.
•  » » » » 2 months ago, # ^ |   0 Could you please share your approaches and codes for 4th question?
•  » » » » 2 months ago, # ^ |   0 I coded 4th in nlogn and it passed.
•  » » » » » 2 months ago, # ^ |   0 Maybe my O(nlogn) implementation was a mess.
•  » » » » » 2 months ago, # ^ |   0 can you please share the solution?
•  » » » » » » 2 months ago, # ^ |   0 I calculated number of times ai and bi will occur in the answer. Just multiplied the count obtained with ai and bi to get the final answer (Contribution technique). Now, for ai to appear in the summation this condition must be true : ai + bj >= aj + bi => ai-bi >= aj-bj Make a vector of ai-bi values and then sort it. Use binary search to count the occurences with the above condition (for count of bi inequality will be reversed).
•  » » » » » » » 2 months ago, # ^ |   0 I figured out this during the contest but couldn't code it up :<( .
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 metoo
•  » » » » » 7 weeks ago, # ^ |   0 can you send the code of 4th quesiton? So that i can see what is the approach of the quesion...
•  » » » » 2 months ago, # ^ |   0 Could you please tell what part was wrong in Problem Statement of 5th Problem?
•  » » » » » 2 months ago, # ^ |   +8 Setter solution didn't ignore double counting.For eg. xj[i] = 3;then possible lengths of jumps are [2^0,2^1] union [2^1,2^2]so,{1,2} union {2,3,4} = {1,2,3,4}but setter solution has taken it as {1,2,2,3,4}
•  » » » » » » 2 months ago, # ^ |   0 Okay cool got it. Thanks!
 » 2 months ago, # | ← Rev. 2 →   0 I had solved first, second and fourth partial. For the first I had just checked if string length is greater than 3 and if s(I) == S(I+1) or S(I) ==S(I+2). For. The second I had separately handled four corner cases and for rest cases just found out operation required to turn minimum of two number to zero and add 2 to itFor fourth partial brute force
 » 2 months ago, # |   0 Can anyone suggest approach for two summation and swap it harder?
•  » » 2 months ago, # ^ | ← Rev. 5 →   +11 This is the solution for Two SummationFirst, in these types of problems, you should try to simplify as much as possible. Let's go through the solution. Part- IYou can take out $A[i] + B[j]$ from the max and the problem would reduce to finding sum of $A[i] + B[j]$ separately and sum of $max(0, A[j]+B[i] - A[i] - B[j])$ Part- IIYou can then calculate the first part by just observing that each number will appear in n pairs, so the sum would be $n \times (Sum(A[i]) + Sum(B[i]))$. Part- IIIFor the other part, see that it can be re-written as $max(0, (A[j]-B[j]) - (A[i]-B[i]))$Make an array Diff, such that $Diff[i] = A[i] - B[i]$, so again rewriting, you need to find summation over all pairs of values in Diff, $max(0, Diff[i] - Diff[j])$.Now how to do this in better than $O(N^2)$? OptimizationSee that since you need to sum it over all pairs, the order does not matter.So you can sort the elements in Diff array. Also, observe that only those pairs will contribute where $Diff[i] > Diff[j]$, others will be $0$.So for each index i (say 0-based), the answer will increase by $(Diff[i]-Diff[0]) + (Diff[i] - Diff[1]) + ... + (Diff[i] - Diff[i-1])$=> $i \times Diff[i] - (Diff[0] + Diff[1] + ... Diff[i-1]) = i \times Diff[i] - (Sum(Diff[j])$ upto $i-1)$Now you just iterate over all indices, keep a sum-upto variable and add the above to the answer. ExampleLet's try to understand this by an example. $Diff = [2, 4, 5, 7]$.So the pairs that will be counted are:$4 - 2 => 4 - (2)$$(5 - 2) + (5 - 4) => 2*5 - (2+4)$$(7 - 2) + (7 - 4) + (7 - 5) => 3*7 - (2+4+5)$ A Little More ObservationAll pairs are of the form $+Diff[i] - Diff[j]$.Q: How many times, a certain index i, will be at '+' position?A: $i$ times, as there are $i$ elements smaller than ith element (0-based).Q: How many times, a certain index $i$, will be at '-' position?A: $n-1-i$ times, as there are $n-1-i$ elements bigger than ith element (0-based).Therefore, for each index $i$, add $i\times Diff[i] - (n-1-i)\times Diff[i] = Diff[i] * (2\times i - n + 1)$. Final Answer$n \times (Sum(A[i]) + Sum(B[i])) + Sum(Diff[j] \times (2j - n + 1))$
•  » » » 2 months ago, # ^ |   +8 This should be O(nlogn) as you have sorted the diff array.
•  » » » » 2 months ago, # ^ |   +1 Yeah, you are right, what I meant was how to do in $O(N)$ after sorting.I'll change that. Thanks!
•  » » » 2 months ago, # ^ |   0 This leetcode problem is based on the similar profile. Even though, I have solved this problem, I couldn't get the 4th one in the contest =(If someone has got similar problems, please do share.
 » 2 months ago, # | ← Rev. 2 →   -8 x
•  » » 2 months ago, # ^ |   +8 I appreciate your effort but it is kind of unreadable.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 y
•  » » » » 2 months ago, # ^ |   0 I did with prefix sums but my approach is different and works in nlogn :)
•  » » 2 months ago, # ^ |   0 Were the points displayed after submission? They weren't displayed for me when my solutions got fully accepted
•  » » » 2 months ago, # ^ |   0 Yes the points were not shown when the solution got fully accepted but for partially correct solution points were shown
 » 2 months ago, # |   +3 crappiest contest wasted 4 hours solved first three only to learn test cases for problem 2 changed and for problem 3 test cases were super weak and wrong . no learning
 » 2 months ago, # |   +8 Can anyone help with the logic of the shipment packaging question?
 » 7 weeks ago, # |   +19 Does anyone know when will they release standings?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 After the second version which is to be held on 23rd Oct . Your best of two scores will be considered in final standings. Source :- LinkedIn
 » 6 weeks ago, # |   0 I have received one mail (some days back) regarding another contest of Codeagon on 17th October. But since then, I haven't received any further notifications. Has anyone else got it?
 » 3 weeks ago, # |   0 When we can expect results of codeagon 2021 ?
•  » » 3 weeks ago, # ^ |   0 It's better to have no expectation from them :XD
•  » » » 3 weeks ago, # ^ |   +3 Looks like they were not too much interested this year.In first contest test cases went wrong for second problem.
•  » » 3 weeks ago, # ^ |   +6 Shortlisting emails are getting released. Check your mailbox.