### jaypalmudaliyar24's blog

By jaypalmudaliyar24, history, 6 weeks ago,

As I didn't find any blog for this round discussion so posting this blog

Problems :

Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6

My opinion :
I found problems harder than the previous version of CodeAgon 2021.

PS : Sorry for unclear photos of problems (if anyone have clear photos please share them in comments)

• +30

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by jaypalmudaliyar24 (previous revision, new revision, compare).
 » 6 weeks ago, # |   +1 This time it was smooth, no mistakes
•  » » 6 weeks ago, # ^ |   +4 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 →   +1 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
•  » » » » 6 weeks ago, # ^ |   0 Did you got ac with that? I got WA with this approach.
•  » » » » » 6 weeks ago, # ^ |   0 yes
•  » » » » » » 6 weeks ago, # ^ |   0 Can you share your code please?
•  » » » » 6 weeks ago, # ^ |   0 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
•  » » » » » 6 weeks ago, # ^ |   0 Shouldn't it be having bitonic nature?
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 6 weeks ago, # ^ |   -8 Can u please share how did you solved it.
•  » » » 6 weeks ago, # ^ |   +8 Vin__ar, Since A[i][0] are at a gap of 4 atleast and there is always a fixed gap between sqrt(A[i][0]) and A[i][1], I feel that taking the first buying day is always optimal. Can you tell me why its wrong
•  » » » » 6 weeks ago, # ^ |   0 Sure, here's a case A = {{12, 47},{36,44}} B = {{100, 48}} Correct me if I'm missing something.
 » 6 weeks ago, # |   +9 Atleast this time I didn't have to guess the setter's solution XD.
 » 6 weeks ago, # | ← Rev. 2 →   0 How to solve problem 1?
•  » » 6 weeks ago, # ^ |   +8 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.
•  » » » 6 weeks ago, # ^ |   +3 I have seen this kind of trick somewhere. Can you please share some problem related to this trick, if you can recall?
•  » » » » 6 weeks ago, # ^ |   +3 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 →   +4 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 →   +3 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?
•  » » 6 weeks ago, # ^ |   0 Codeint dp[1001][1001]; 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:"<
•  » » » 6 weeks ago, # ^ |   0 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 →   0 I didn't get your point, are you saying loop is not required for input greater tha 2 or 3?
•  » » » » » 6 weeks ago, # ^ |   0 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.
•  » » » » » » 6 weeks ago, # ^ |   0 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.
 » 6 weeks ago, # |   +3 Did anyone solve 4+ ?
 » 6 weeks ago, # |   0 How many could you solve? Me 4 (1,2,5,6).
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 What's the approach for Problem 5 ?
•  » » 6 weeks ago, # ^ |   0 Can you state how to solve problem 5
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 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
•  » » » » 6 weeks ago, # ^ |   0 Thnx mate.
 » 6 weeks ago, # |   +9 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[20]; 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][1]=Z-sqrt(A[i][0]) to observe according to this, if $A[i][0]=A[j][1]$. Usually in such problems, if we consider any $B[k]$ such that $B[k][0]>A[j][0]$, then, the function $F(x)=(B[k][0]-A[x][0])*(B[k][1]-A[x][1])$ 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][0] pq=new PriorityQueue(new Comparator(){ public int compare(int o1[],int o2[]) { if(o1[0]>o2[0]) return 1; else if(o1[0]==o2[0]) { if(o1[1]>o2[1]) return 1; else return -1; } else return -1; }}); HashMap ha=new HashMap<>(),hb=new HashMap<>(); for(int x[]:A) ha.put(x[0],Math.min(ha.getOrDefault(x[0],Integer.MAX_VALUE),x[1])); for(int x[]:B) hb.put(x[0],Math.max(hb.getOrDefault(x[0],Integer.MIN_VALUE),x[1])); 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]==1) buy.add(new int[]{p[0],p[2]}); 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[0]-buy.get(mid1)[0])*(p[2]-buy.get(mid1)[1]),v2=1l*(p[0]-buy.get(mid2)[0])*(p[2]-buy.get(mid2)[1]); 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[0]-buy.get(l)[0])*(p[2]-buy.get(l)[1])); l++; } } } return ans; } } If you have any suggestions and/or cases where my approaches fail, do let me know.
•  » » 6 weeks ago, # ^ |   0 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)
 » 6 weeks ago, # |   0 Did anyone solve all the problems?
 » 6 weeks ago, # |   +15 Any information about ranklist?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 From Scaler By InterviewBit Discord ServerDiscord Link
 » 5 weeks ago, # |   -16 any information on ranklist?I guess they cancelled the result of both contest for obvious reasons