### golions's blog

By golions, history, 11 months 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 Comments (49)
 » Auto comment: topic has been updated by golions (previous revision, new revision, compare).
 » golions orz
 » 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$.
•  » » 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.
•  » » » Yes, you do. Sorry, forgot to include that inside the solution. Good catch.
•  » » » » Cool. Thanks for sharing this solution!
•  » » Can you please elaborate a bit, why we used min().
•  » » » $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.
•  » » » » Thanks, I got it.
•  » » 11 months ago, # ^ | ← Rev. 3 →   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.
•  » » » $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$ to be 2, it means that the character 4 blocks above $arr$ 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.
•  » » » » Got it, great solution!
•  » » 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.
•  » » This is the best solution I found. The official solution was very poorly written.
 » 11 months ago, # | ← Rev. 4 →   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++)
 » 11 months ago, # | ← Rev. 2 →   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.)
•  » » Is this idea managable to pass TL. I thought to implement this idea then saw TL 1 second and gave up.
•  » » 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
 » 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.
•  » » 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
 » 11 months ago, # | ← Rev. 2 →   You can check out my video solutions (A — D) here:https://youtu.be/NMbqtVdVZqI
 » 11 months ago, # | ← Rev. 4 →   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; } } 
•  » » what a super duper big hand you have =)))))
 » orz
 » i think you should make unofficial questions so that we can understand what question wants from us.
 » can we apply binary search in C??
•  » » yes I used binary search .
•  » » » Hey,can u plzzz share the approach
•  » » » » see my code u will understand https://codeforces.com/contest/1393/submission/89488619
 » The explanation of C is daaam good! Thank you for doing the hard work
 » thank you brother for the solutions :)
 » Mindblowing explanation for problem C kudos
 » Problem C Explaination is MIND_BLOWINGThanks golions
 » upperleft[k][j]=min(upperleft[k−1][j],upperleft[k][j−1]) i think a +1 is missing here
•  » » Yes, thank you for pointing that out.
 » 11 months ago, # | ← Rev. 2 →   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
 » 11 months ago, # | ← Rev. 2 →   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.
 » You missed adding 1 in the DP update of last solution.
•  » » Yes, thank you for pointing that out.
 » Auto comment: topic has been updated by golions (previous revision, new revision, compare).
 » This editorial was far better than codeforces editorial thanks for this editorial :)
 » 10 months ago, # | ← Rev. 2 →   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.
•  » » can u explain problem c using binary search
•  » » » 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
•  » » » » lrvideckis I cnt understand how that possible function in your code is working (the sub-problem). Can you explain its logic?
•  » » » » » I resubmitted with more comments: 94602302
 » Better than official
 » 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.
 » Very good editorial.Thanks a lot brother