### jaypalmudaliyar24's blog

By jaypalmudaliyar24, history, 6 weeks ago,   Comments (37)
 » Auto comment: topic has been updated by jaypalmudaliyar24 (previous revision, new revision, compare).
 » This time it was smooth, no mistakes
•  » » Not exactly, problem D had weak test cases, always buying the stock on first possible day worked for one of my friend, which is clearly wrong.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   Was the intended solution, getting an expression in terms of sqrt(y), and then differentiation and solving quadratic to get the global maxima? I did that
•  » » » » Did you got ac with that? I got WA with this approach.
•  » » » » » yes
•  » » » » » » Can you share your code please?
•  » » » » Differentiating was not necessary, the fact that you got quadratic was enough to claim that one of the extreme values in A would give maximum for a fixed B. so just do these 2*m checks
•  » » » » » Shouldn't it be having bitonic nature?
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   My bad, what I said above is incorrect. I substituted buying date as 4*b*b and buying price as Z — 2*b, which when i plug into the profit expression gives a cubic with negative leading term. So I should have checked the least buying date, latest buying date, and second extremum of this cubic (for each choice of selling quotation), but i guess due to weak tests checking the least and latest buying date itself ACed.
•  » » » » » Can u please share how did you solved it.
•  » » » Vin__ar, Since A[i] are at a gap of 4 atleast and there is always a fixed gap between sqrt(A[i]) and A[i], I feel that taking the first buying day is always optimal. Can you tell me why its wrong
•  » » » » Sure, here's a case A = {{12, 47},{36,44}} B = {{100, 48}} Correct me if I'm missing something.
 » Atleast this time I didn't have to guess the setter's solution XD.
 » 6 weeks ago, # | ← Rev. 2 →   How to solve problem 1?
•  » » For every market $i$, you can either buy the oranges from the same market or go to one of the markets $j$, connected to it, get the oranges in minimum possible cost from $j$ and come back to $i$. This will incur an extra cost of $cost_{ij}$ + $d*cost_{ij}$. You can solve this using Dijkstra's algorithm. Imagine, there is a virtual node connected to all the markets and edge cost is $b_i$. Also multiply all the original edge weights by $d+1$. Problem then reduces to finding shortest path from that virtual node to all other nodes.
•  » » » I have seen this kind of trick somewhere. Can you please share some problem related to this trick, if you can recall?
•  » » » » Sorry, couldn't recall any problem. But generally when I have a solution that is dp but the transitions make a graph with cycles, I try to think if updating the states in the correct order is possible through Dijkstra. So, for this problem, I initially thought $ans_i = min(ans_j + (d+1)*cost(i,j))$. Then realized that the updates are possible through Dijkstra. That virtual node is a common implementation trick, you can just ignore that and initialize $ans_i = b_i$ and then do the relaxations in Dijkstra.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   This is the exact same problem of Codeagon 2020. problem 1 Just replace the edge weights with cost * (D + 1). Rest everything is exactly the same. And it's more funny when you find the problem on code forces that they copied from in 2020, which they repeated now. link
 » 6 weeks ago, # | ← Rev. 2 →   In problem 2, I wrote dp[A][A]. dp[i][j] denotes I have written i lines and selected j lines which I can paste and then the transitions were easy. Can someone tell me was there any other obvious method to solve this problem?
•  » » Codeint dp; int rec(int copied, int prev, int A){ // clog<<"rec:"< A)return inf; if(copied == A)return 0; if(dp[copied][prev] != -1)return dp[copied][prev]; int rem = A - copied; int temp = inf; for(int i=1; i<=min(rem, copied); i++){ if(i == prev){ temp = min(temp, 1 + rec(copied+i, i, A)); }else{ temp = min(temp, i + 1 + rec(copied+i, i, A)); } } int all = 2 + rec(2*copied, copied, A); //1 + 1 int old = inf; // if(prev > 0) // old = 1 + rec(copied+prev, prev, A); // clog<<"ret:"<
•  » » » Actually, you don't need to do the loop for more than 2 or 3 copies. I have no formal proof of it, just by intuition I wrote this.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   I didn't get your point, are you saying loop is not required for input greater tha 2 or 3?
•  » » » » » Can you please explain your dp states and what you are doing in the loop first? I was saying that if you have already copied x lines from the previous step, then there is one possibility to copy j lines from the top (j varies from 1 to the current number of lines written till now) and it will cost j+1. For this j, I am saying that the max value of j can be 2-3. You just need to copy not more than 2-3 lines using this operation as it's always better to use other cheaper methods.
•  » » » » » » In the loop i am iterating from 1 to number of copies already made, i.e the first option where we can copy X lines from top. I tried iterating from 1 to 3 as you mentioned, but it is giving WA.
 » Did anyone solve 4+ ?
 » How many could you solve? Me 4 (1,2,5,6).
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   What's the approach for Problem 5 ?
•  » » Can you state how to solve problem 5
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   My approachSo lets say we are at index $i ∈ (1<=i x=min(h1,h2), y=max(h1,h2)$$p1=B[i], p2=B[i+1]$ and initially $ans=0$ if$(p2=p1+1) =>$ we can't place a woodblock else if$(y-x >= p2-p1-1) =>$ even if we place the woodblock from x in increasing manner we can only reach the height of $x+(p2-p1-1)$ so $ans=max(ans,x+p2-p1-1)$ otherwise, we can place the wooden block from $x$ until we get height of $y$ then we can form a pyramid from either side if remaining places are odd then we can have max height of $y + (remaining/2 + 1)$ else we can have $y + (remaining / 2)$ height so $rem = p2-p1-1-(y-x) , ans = max(ans,y+(rem+1)/2)$ so we can iterate over the array and find max achievable height in $O(n)$ If you find anything wrong correct me
•  » » » » Thnx mate.
 » What are your approaches for problems 3 and 4? Here are mine- Problem 3The problem asks us to find the permutation of A that will generate the lexicographically largest array $X$. We know how we can solve this, if the array was binary (by sorting in non-increasing order). We do a similar thing, but with a twist. For any range of array elements, we can divide it into 2 parts, a good part, where the integers have $i^{th}$ bit is set, and a bad part, for the remaining integers. This is nothing but divide and conquer. We iterate through a range, cluster good values first and bad values later, and then iterate through the sub ranges for lower bits. For example we have a range $[x,y]$. There are $z$ good elements for bit position $i$. So we will generate the ans for bit $i+1$ for ranges $[x,x+z], [x+z+1,y]$.Now how do we combine our answers for bit $i+1$? We can see that if a bad segment exists(for a particular set bit) in between 2 good segments, then the right segment will not contribute to the answer. So we combine values if and only if the entire segment is good for the set bit. In other words, for range $[x,y]$, if good elements is $k$, then, $ans[i+1] = (k==z) ? z + good[x+z+1,y] : k$ Finally, $X[i]$ will be the value at $ans[20-i]$ for range $[1,n]$ The following AC code uses the same thing in an iterative way. codepublic class Solution { public int[] solve(int[] a) { int i,n=a.length,ans[]=new int; ArrayList al=new ArrayList<>(); ArrayList> r=new ArrayList<>(); for(int x:a) al.add(x); r.add(al); for(i=0;i<20;i++) { ArrayList> te=new ArrayList<>(); int b=19-i; boolean can=true; for(ArrayList x:r) if(can) { ArrayList good=new ArrayList<>(); ArrayList bad=new ArrayList<>(); //ranges based on previous clusterings for(int v:x) if(((v>>b)&1)==1) good.add(v); else bad.add(v); if(bad.size()>0) can=false; ans[i]+=good.size(); te.add(good); te.add(bad); } else te.add(x); r=te; } return ans; } }  Problem 4Given an array of cost prices $A$, and sell prices $B$, find maximum profit on buying and selling stock at most once.I used the constraint A[i]=Z-sqrt(A[i]) to observe according to this, if $A[i]=A[j]$. Usually in such problems, if we consider any $B[k]$ such that $B[k]>A[j]$, then, the function $F(x)=(B[k]-A[x])*(B[k]-A[x])$ is an increasing-decreasing (or decreasing-increasing, but given we needed to find maximum here, I was kinda sure of the former) function for $x \in [0,sz]$ where $sz$ is the number of quotations with \$A[j] pq=new PriorityQueue(new Comparator(){ public int compare(int o1[],int o2[]) { if(o1>o2) return 1; else if(o1==o2) { if(o1>o2) return 1; else return -1; } else return -1; }}); HashMap ha=new HashMap<>(),hb=new HashMap<>(); for(int x[]:A) ha.put(x,Math.min(ha.getOrDefault(x,Integer.MAX_VALUE),x)); for(int x[]:B) hb.put(x,Math.max(hb.getOrDefault(x,Integer.MIN_VALUE),x)); for(int x:ha.keySet()) pq.add(new int[]{x,1,ha.get(x)}); for(int x:hb.keySet()) pq.add(new int[]{x,-1,hb.get(x)}); long ans=0; ArrayList buy=new ArrayList<>(); while(!pq.isEmpty()) { int p[]=pq.poll(); if(p==1) buy.add(new int[]{p,p}); else { int l=0,r=buy.size()-1; while(r-l>5) { int mid1=l+(r-l)/3,mid2=r-(r-l)/3; long v1=1l*(p-buy.get(mid1))*(p-buy.get(mid1)),v2=1l*(p-buy.get(mid2))*(p-buy.get(mid2)); ans=Math.max(ans,v1); ans=Math.max(ans,v2); if(v1>v2) r=mid2; else l=mid1; } while(l<=r) { ans=Math.max(ans,1l*(p-buy.get(l))*(p-buy.get(l))); l++; } } } return ans; } } If you have any suggestions and/or cases where my approaches fail, do let me know.
•  » » For 3rd, I think one can simulate the following greedy procedure:Take the maximum element = maxxPop all occurences of it, and add them to the permutation.Update all remaining values as x &= maxx.Repeat.You will have to do this at most 20 times.The reason this works is because at each step, we are selecting the lexicographically largest element according to the current active bitmask(mask of bits which have still not encountered a 0)
 » Did anyone solve all the problems?