### golions's blog

By golions, history, 7 weeks ago,

Hello everyone! At the time I am writing this, there is still no editorial for Round #662. I did very well on this contest and I think my solutions are interesting, so hopefully this can help some people.

Problem A

Code (Java): 89214023

Problem B

Code (Java): 89220791

1393C - Pinkie Pie Eats Patty-cakes

Problem C

Code (Java): 89231755

1393D - Rarity and New Dress

Problem D

Code (Java): 89257786

• +229

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by golions (previous revision, new revision, compare).
 » 7 weeks ago, # |   +11 golions orz
 » 7 weeks ago, # |   +55 Great solutions! However, there exists a shorter solution for D.Let $dp[i][j$] be the number of dress patterns where $i, j$ is the bottom-most vertex.Then, $dp[i][j] = 1 + min (dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j])$. 1 is added at the beginning as it is the case that the point $i, j$ is a solution, and min() is the furthest the pattern exists in the right, top, and left directions.Note that $2 <= i < n$ and $1 <= j < n-1$.
•  » » 7 weeks ago, # ^ |   +8 Do you have to check for $\verb#board#[i-1][j-1] == \verb#board#[i-1][j] == \verb#board#[i-1][j+1] == \verb#board#[i-2][j] == \verb#board#[i][j]$ before doing the dp state? Just making sure that I understand your solution correctly.
•  » » » 7 weeks ago, # ^ |   +15 Yes, you do. Sorry, forgot to include that inside the solution. Good catch.
•  » » » » 7 weeks ago, # ^ |   +5 Cool. Thanks for sharing this solution!
•  » » 7 weeks ago, # ^ |   0 Can you please elaborate a bit, why we used min().
•  » » » 7 weeks ago, # ^ |   +4 $dp[i - 1][j - 1]$ shows how far in the left direction the dress can extend. Similarly, $dp[i - 1][j + 1]$ is for the right direction, and $dp[i - 2][j]$ is for the up direction. We take min() of these values because when we cannot extend one of these directions, we cannot extend $dp[i][j]$ any more. If we choose a value greater than the min(), in the direction that the min() of the values is facing, the letters would be different from the current letter.
•  » » » » 7 weeks ago, # ^ |   0 Thanks, I got it.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Why this transition won't work for problem D? (with appropriate checks that the characters are same): dp[i][j]=1+min(dp[i−1][j−1],dp[i−1][j+1],dp[i−1][j]) It gives correct output for first 3 testcases, but fails on 4th one.
•  » » » 7 weeks ago, # ^ |   +6 $dp[i - 1][j]$ should be $dp[i - 2][j]$. There is actually parity difference — you can see this by drawing the graph out. Look at the biggest picture provided in the statement. If we want $dp[5][4]$ to be 2, it means that the character 4 blocks above $arr[5][4]$ must also be 'd'. This is not checked when you call $dp[i - 1][j]$. In other words, $dp[i - 1][j]$ does not check enough nodes in the upward direction.
•  » » » » 7 weeks ago, # ^ |   0 Got it, great solution!
•  » » 7 weeks ago, # ^ |   -8 This is one hell of a thought process man! I saw many red coders struggle with this problem, but you saw through it. Kudos for this great observation and thanks a lot for sharing it.
•  » » 7 weeks ago, # ^ |   0 This is the best solution I found. The official solution was very poorly written.
 » 7 weeks ago, # | ← Rev. 4 →   +24 Nice work! I have an alternate solution for B:Note that since $1$ $\leq$ $a_i$ $\leq$ $10^5$, and similarly for $x$, we can store the frequencies of each plank length in an array aptly named $freq$, and increase/decrease it as we gain/remove plank lengths of that type.We can store the amount of lengths that have frequencies of $2s$ and $4s$ in separate variables, with each stick's frequency contributing $\lfloor{\frac{freq_i}{2}}\rfloor$ and $\lfloor{\frac{freq_i}{4}}\rfloor$ respectively. Note that the amount of $2s$ and $4s$ aren't mutually exclusive, and must be accounted for at the end.After each operation, we must check whether the number of $2s$ and $4s$ are changed. This can be done easily by checking: if $freq_i$ is increased and is now equal to $0$ $(mod$ $2)$, then the number of $2s$ is increased. if $freq_i$ is increased and is now equal to $0$ $(mod$ $4)$, then the number of $4s$ is increased. if $freq_i$ is decreased and is now equal to $1$ $(mod$ $2)$, then the number of $2s$ is decreased. if $freq_i$ is decreased and is now equal to $3$ $(mod$ $4)$, then the number of $4s$ is decreased. This is because when an integer is increased from $k-1$ $(mod$ $k)$ to $0$ $(mod$ $k)$, it is divisible an "extra" time when performing floor division. The opposite is also true for when an integer is decreased from $0$ $(mod$ $k)$ to $k-1$ $(mod$ $k)$.Finally, to answer each query, we must check if both $fours$ $\geq$ $1$, and $twos - 2$ $\geq$ $2$. This is to account for the planks used for the squares, the $4s$ being included in the number of $2s$. If this condition is true, we print "Yes", otherwise "No".A link to my submission (C++)
 » 7 weeks ago, # | ← Rev. 2 →   +17 Nice solutions!I had an alternate approach for D, which I thought was interesting even if it might not be the most elegant. My ideaLet's define the one-square pattern as a size $1$ pattern, the five-square pattern as a size $2$ pattern, and so on.Now, let's consider patterns that are centered at each cell individually. Note that if a pattern of size $n$ centered at a cell $(a, b)$ exists, then every single pattern of size $1$ to $n-1$ centered at a cell $(a, b)$ also exists. Therefore, to count all the patterns, it suffices to calculate the largest pattern centered at each cell.Next, note that a pattern of size $n$ centered at $(a, b)$ contains all the cells that are a Manhattan distance of $n-1$ or less away from $(a, b)$. So, in order for a pattern of size $n$ to exist at $(a, b)$, every single cell that is a Manhattan distance of $n-1$ or less away from $(a, b)$ must be the same color as $(a, b)$. This means that, for a cell $(a, b)$, the size of the largest pattern that is centered at that cell is equal to the smallest Manhattan distance between $(a, b)$ and any cell that is not the same color as $(a, b)$.We can use a multi-source BFS to calculate this value for all the cells. Let's define a "boundary" cell as a cell that is either on the edge of the grid or that is not surrounded on all four sides by cells of the same color. These cells all have values of $1$. We then just BFS from all the "boundary" cells and update the values for all the remaining cells. The sum of all the values is the answer.My solution (Java)(Since the TL was 1 second, I had to make several optimizations to make the BFS run in time. I eventually ended up using an array with two pointers as my queue, which made it work.)
•  » » 7 weeks ago, # ^ |   0 Is this idea managable to pass TL. I thought to implement this idea then saw TL 1 second and gave up.
•  » » 7 weeks ago, # ^ |   0 I had the same idea, though I used DP insteadIdeally the recurrence for $dp[i][j]$ would be: $dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i-1][j], dp[i][j-1])$(You also have to check whether the up/right/down/left characters are same for each DP direction, i.e. $board[i][j] == board[i-1][j]$ for $dp[i-1][j]$)However, where do you start? The key is that you do 2 passes, one from the top left corner towards the bottom right corner and one from the bottom right corner towards the top left corner.First pass: $dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])$ Second pass: $dp[i][j] = max(dp[i][j], 1 + min(dp[i+1][j], dp[i][j+1])$It's a bit tricky to understand why this works, but consider the corners of any rectangle in the grid (with the grid extending further out than shown): ........... .a.......b. ........... .c.......d. ........... Suppose that for cell a, the closest different character is at cell d. In the 1st pass, we update $dp[d_r][d_c] = 1$ because the character above and to the left are different (otherwise cell d wouldn't have the closest different character from cell a). Then, in the 2nd pass, we update the cells on the shortest path from cell d to a in the order of the actual path since we're moving up and left in our DP pass.Now suppose that for cell 'c', the closest different character is at cell 'b'. In the 1st pass, we update $dp[b_r][b_c] = 1$ because the character below and to the left are different (same reasoning as above). Also in the 1st pass, we update the cells on the shortest path from b to d. We know that cell b is the closest different character to cell d since if there were a closer one, it would also be the closest different character to cell c. Finally, in the 2nd pass, we update the cells in the shortest path from d to c.You can find similar arguments for the other corner combinations, but I'll leave that as an exercise for the reader.My submission
 » 7 weeks ago, # |   +3 golions Can you mention the binary_search + priority_queue solution that people have solved it with. Intuitively, I thought of that solution but couldn't come up with it. Hope you explain it.
•  » » 7 weeks ago, # ^ |   0 I thought about binary search for a long time in contest but I didn't find a solution. Here is someone else's comment about how to solve C with binary search and priorityqueue: https://codeforces.com/blog/entry/81216?#comment-677558
 » 7 weeks ago, # | ← Rev. 2 →   +5 You can check out my video solutions (A — D) here:https://youtu.be/NMbqtVdVZqI
 » 7 weeks ago, # | ← Rev. 4 →   0 I solved A by simply finding a pattern: 3 -> 2 4 -> 3 5 -> 3 6 -> 4 ...My approach for B was to keep a map and then have three lists: pairs of same numbers (pair), quadruplets of same numbers (quad), and a list of numbers with more than 7 occurrences (many). Then there are three cases to check, using just one element from the "many" list to make two squares right off the bat, using two elements from the "quad" list to make two squares, and finally using one element from the "pair" and one element from the "quad" list to make a rectangle and a square. One thing to keep track of was making sure that you don't use the same number more than it can be used, but you can just do some simple conditional checking to account for that. I did C by binary searching for the answer. Each time, I would do a validity check by maintaining a queue to keep track of the "unusable" ones. I would loop through each of the n spots and remove and add from the unusable accordingly and then always put the maximum occurrence number. Then, if the map ever turns empty, then return "not valid".IMPLEMENTATIONS [JAVA] (Might be a bit messy as I am not the best implementer) Problem A import java.io.*; import java.util.*; public class chesss { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter writer = new PrintWriter(System.out); int t = Integer.parseInt(in.readLine()); for(int i = 0; i < t; i++){ int size = Integer.parseInt(in.readLine()); if(size % 2 == 0){ writer.println(size - (size/2 - 1)); } else{ writer.println(size - ((size - 1)/2)); } } writer.close(); in.close(); } }  Problem B import java.io.*; import java.util.*; public class building { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter writer = new PrintWriter(System.out); int n = Integer.parseInt(in.readLine()); StringTokenizer st = new StringTokenizer(in.readLine()); TreeMap sizes = new TreeMap<>(); for(int i = 0; i < n; i++){ int length = Integer.parseInt(st.nextToken()); if(!sizes.containsKey(length)){ sizes.put(length, 1); } else{ sizes.put(length, sizes.get(length) + 1); } } TreeSet pair = new TreeSet<>(), quad = new TreeSet<>(), many = new TreeSet<>(); for(int i: sizes.keySet()){ if(sizes.get(i) > 1 && sizes.get(i) < 4){ pair.add(i); } else if(sizes.get(i) > 1 && sizes.get(i) < 8){ pair.add(i); quad.add(i); } else if(sizes.get(i) > 7){ pair.add(i); quad.add(i); many.add(i); } } int q = Integer.parseInt(in.readLine()); for(int i = 0; i < q; i++){ st = new StringTokenizer(in.readLine()); char type = st.nextToken().charAt(0); int amount = Integer.parseInt(st.nextToken()); if(type == '+'){ if(!sizes.containsKey(amount)){ sizes.put(amount, 1); } else{ sizes.put(amount, sizes.get(amount) + 1); if(sizes.get(amount) > 1 && sizes.get(amount) < 4){ pair.add(amount); } else if(sizes.get(amount) > 1 && sizes.get(amount) < 8){ pair.add(amount); quad.add(amount); } else if(sizes.get(amount) > 7){ pair.add(amount); quad.add(amount); many.add(amount); } } } else{ if(sizes.get(amount) == 1){ sizes.remove(amount); pair.remove(amount); quad.remove(amount); many.remove(amount); } else if(sizes.get(amount) == 2){ pair.remove(amount); quad.remove(amount); many.remove(amount); sizes.put(amount, sizes.get(amount) - 1); } else if(sizes.get(amount) == 4){ quad.remove(amount); many.remove(amount); sizes.put(amount, sizes.get(amount) - 1); } else if(sizes.get(amount) == 8){ many.remove(amount); sizes.put(amount, sizes.get(amount) - 1); } else{ sizes.put(amount, sizes.get(amount) - 1); } } if(many.size() > 0){ System.out.println("YES"); continue; } if(quad.size() > 1){ System.out.println("YES"); continue; } if(quad.size() == 1){ int num = sizes.get(quad.first()); if(num - 4 < 2 && pair.size() > 2){ System.out.println("YES"); continue; } if(num - 4 > 1 && pair.size() > 1){ System.out.println("YES"); continue; } } System.out.println("NO"); } writer.close(); } }  Problem C import java.io.*; import java.util.*; public class pinkiePie { static TreeMap> templ = new TreeMap<>(new sort1()); public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine()); for(int i = 0; i < t; i++){ templ.clear(); int n = Integer.parseInt(in.readLine()); int[] arr = new int[n]; StringTokenizer st = new StringTokenizer(in.readLine()); List occs = new ArrayList<>(); for(int j = 0; j < n; j++){ arr[j] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr); for(int j = 0; j < n; j++){ int index = j, cnt = 0; while(index < n && arr[index] == arr[j]){ index++; cnt++; } j = index - 1; occs.add(new occ(arr[j], cnt)); } for(occ j: occs){ TreeSet put; if(!templ.containsKey(j.occurrences)){ put = new TreeSet<>(); } else{ put = templ.get(j.occurrences); } put.add(j.num); templ.put(j.occurrences, put); } occs.sort(new sort()); System.out.println(solve(occs, n)); } } static int solve(List occs, int n){ int ans = 0; int lb = 0, ub = n; while(lb != ub){ int m = (lb + ub)/2; if(good(occs, n, m)){ lb = m + 1; ans = Math.max(ans, m); } else{ ub = m; } } return ans; } static boolean good(List occs, int n, int gap){ TreeMap> map = new TreeMap<>(new sort1()); for(int i: templ.keySet()){ TreeSet put = new TreeSet<>(templ.get(i)); map.put(i, put); } Queue unusable = new LinkedList<>(); int[] fill = new int[n]; for(int i = 0; i < gap; i++){ if(map.isEmpty()){ return false; } fill[i] = map.get(map.firstKey()).first(); unusable.add(new occ(map.get(map.firstKey()).first(), map.firstKey())); map.get(map.firstKey()).remove(map.get(map.firstKey()).first()); if(map.get(map.firstKey()).size() == 0){ map.remove(map.firstKey()); } } for(int i = gap; i < n; i++){ if(map.isEmpty()){ return false; } fill[i] = map.get(map.firstKey()).first(); occ addBack = unusable.poll(); unusable.add(new occ(map.get(map.firstKey()).first(), map.firstKey())); map.get(map.firstKey()).remove(map.get(map.firstKey()).first()); if(map.get(map.firstKey()).size() == 0){ map.remove(map.firstKey()); } if(addBack != null && addBack.occurrences > 1){ //add the latest unusable occ into the map if(map.containsKey(addBack.occurrences - 1)){ map.get(addBack.occurrences - 1).add(addBack.num); } else{ TreeSet put = new TreeSet<>(); put.add(addBack.num); map.put(addBack.occurrences - 1, put); } } } return true; } } class occ implements Comparable{ int num, occurrences; public occ(int num, int occurrences){ this.num = num; this.occurrences = occurrences; } public int compareTo(occ other){ return other.num - this.num; } } class sort implements Comparator{ public int compare(occ a, occ b){ return b.occurrences - a.occurrences; } } class sort1 implements Comparator{ public int compare(Integer a, Integer b){ return b - a; } } 
•  » » 7 weeks ago, # ^ |   +1 what a super duper big hand you have =)))))
 » 7 weeks ago, # |   0 orz
 » 7 weeks ago, # |   0 i think you should make unofficial questions so that we can understand what question wants from us.
 » 7 weeks ago, # |   +3 can we apply binary search in C??
•  » » 7 weeks ago, # ^ |   0 yes I used binary search .
•  » » » 7 weeks ago, # ^ |   0 Hey,can u plzzz share the approach
•  » » » » 7 weeks ago, # ^ |   0 see my code u will understand https://codeforces.com/contest/1393/submission/89488619
 » 7 weeks ago, # |   +6 The explanation of C is daaam good! Thank you for doing the hard work
 » 7 weeks ago, # |   +6 thank you brother for the solutions :)
 » 7 weeks ago, # |   +6 Mindblowing explanation for problem C kudos
 » 7 weeks ago, # |   +5 Problem C Explaination is MIND_BLOWINGThanks golions
 » 7 weeks ago, # |   +6 upperleft[k][j]=min(upperleft[k−1][j],upperleft[k][j−1]) i think a +1 is missing here
•  » » 7 weeks ago, # ^ |   0 Yes, thank you for pointing that out.
 » 7 weeks ago, # | ← Rev. 2 →   +5 In problem D, I considered the rhombus as two triangles: left and right.For each cell $(i,j)$, I calculated two values: $b_{i,j}$ = Max size of the left triangle if this cell is the centre of the rhombus $c_{i,j}$ = Max size of the right triangle if this cell is the centre of the rhombus Then, $m_{i,j}$ = $min(b_{i,j},c_{i,j})$ is the max size of a rhombus centered in this cell.The final answer is the sum of all $m_{i,j}$.To calculate $b_{i,j}$ and $c_{i,j}$, we need: $up_{i,j}$ = Number of cell with same color above this cell $dn_{i,j}$ = Number of cell with same color below this cell $a_{i,j}$ = $min(up_{i,j},dn_{i,j})$ Then, $b_{i,j}$ and $c_{i,j}$ can be calculated easily using $a_{i,j}$ and dynamic programming: $b_{i,j}$ = $min(a_{i,j},b_{i,j-1})+1$ $c_{i,j}$ = $min(a_{i,j},c_{i,j+1})+1$ This solution includes calculations of several arrays, but each of them can be calculated using simple iteration.My submission
 » 7 weeks ago, # | ← Rev. 2 →   0 Why is not it enough to have just 2 counters to solve problem B? oOI have solved the problem this way and the editorial slightly confused me.
 » 7 weeks ago, # |   +6 You missed adding 1 in the DP update of last solution.
•  » » 7 weeks ago, # ^ |   0 Yes, thank you for pointing that out.
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by golions (previous revision, new revision, compare).
 » 7 weeks ago, # |   +6 This editorial was far better than codeforces editorial thanks for this editorial :)
 » 7 weeks ago, # | ← Rev. 2 →   +3 My Proof for DIV2 C,extending your logicLet us assume that there are max-1 boxes and we have to fill them with numbers, and we have to maximize the size of the smallest box, let us first ensure that size of all boxes are 1, we have a list of frequences say cnt1 , cnt2 , ... but none of these are greater than the number of boxes so let us distribute the first number equally among boxes, if we run out of the first number, let us take the next number and start distributing them equally ( i.e one number per box), by the time we complete the first round we would have exhausted a few numbers, and no box is empty now, size of each box is 1 and we would have used max-1 numbers it reduces to the same problem again, so we can proceed with the same algorithm ,no 2 numbers in the same box will be identical and we can always rearrange numbers within a box to ensure they are max apart.
•  » » 7 weeks ago, # ^ |   0 can u explain problem c using binary search
•  » » » 7 weeks ago, # ^ |   +1 Given a distance D, can you place cakes in some order such that the distance between any 2 cakes of the same filling is >= D?To solve this sub-problem, we employ a constructive alg:let's say you're choosing which cake to place on the i-th iteration, among all cakes which are valid (previous cake of same filling is >= D away), greedily place the cake with the max # of occurrences remaining.Now, we want to find largest D such that there exists some ordering of cakes. We can find max D with binary search89236305
•  » » » » 7 hours ago, # ^ |   0 lrvideckis I cnt understand how that possible function in your code is working (the sub-problem). Can you explain its logic?
 » 6 weeks ago, # |   0 Better than official
 » 6 days ago, # |   +6 Better explanations than the original editorial. Especially in problem B. Thanks a ton for this. If someone wants implementation of the above in C++, here is my solution.