Educational Codeforces Round 62 Editorial

1140A - Detective Book

1140B - Good String

1140C - Playlist

1140D - Minimum Triangulation

1140E - Palindrome-less Arrays

1140F - Extending Set of Points

1140G - Double Tree

Comments (69)

• 3 years ago, # ^ |

  ← Rev. 2 →  

  +4

  Because long somtimes is just int. So to prevent this mistake everytime write "long long". UPD: When you think int isn't enough

  • 3 years ago, # ^ |

    Thanks

  • 13 months ago, # ^ |

    This is very true.

• 3 years ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 3 years ago, # ^ |

    @bhatnagar.mradul bro u are trying to implement that greedy solution using dp.. i dont mean that..

    i want to know that O(n^3) solution using recursive dp

    • 3 years ago, # ^ |

      dp(i,j)=min(dp(i,k)+dp(k,j)+i*k*j) for all k varies from i+1 to j-1 partition the polygon into two polygon (i,k) and (k,j) and one triangle

    • 3 years ago, # ^ |

      I used O(N^2) dp

      dp[i][j] means answer for polygon that is made from this points -> [1,2...i] and [n,n-1,...j].

      dp[i+1][j]=min(dp[i+1][j],dp[i][j]+i*(i+1)*j)
      dp[i][j-1]=min(dp[i][j-1],dp[i][j]+i*(j-1)*j)

      You need to update answer when i+1==j-1.
      My solution.

• 3 years ago, # ^ |

  ← Rev. 2 →  

  +7

  Keep two pointers as state. dp[i][j] should have the optimal total cost of triangulation of the polygon with { i, i+1, i+2, ..., j-1, j } vertices. To calculate dp[i][j] you have to take the line i-j at some point in a triangle. Pick a vertex k such that i < k < j and make a triangle { i, j, k }.

  So dp[i][j] = min { i*j*k + dp[i][k] + dp[k][j] } for all k such that i < k < j.

  Result is dp[1][n]. Code if needed.

• 3 years ago, # ^ |

  ← Rev. 2 →  

  +10

  I tried, but I haven't managed to squeeze my O(q1.5)O(q1.5) implementation in time limit. But it doesn't mean that it's impossible, considering my optimization skills.

  Sometimes actually O(q1.5logq)O(q1.5log⁡q) version can be faster, maybe I'll try that.

• 3 years ago, # ^ |

  can I find any tutorial for that ?

• 3 years ago, # ^ |

  you can insert pair, with second equal to index, this guaranties uniqueness.

  • 2 months ago, # ^ |

    I have used multiset but it gives TLE, Although set and multiset have same time complexity. Can you say it why that happens?

• 3 years ago, # ^ |

  when l is odd then (**#**) you can't split it into tow same segment . the different of those just that .

  • 3 years ago, # ^ |

    I mean we can use recipe when l is even for both case,can't we?

    • 3 years ago, # ^ |

      You can, but it will drop complexity from O(logl)O(log⁡l) to O(l)O(l). It doesn't matter in this specific task, but it worse overall.

• 3 years ago, # ^ |

  If you have palindrome of size ODDNUMBER, you also have palindrome of size ODDNUMBER — 2. So you just avoid palindromes of length 3 and that's enough.

  Split the array A into two smaller arrays ODD and EVEN, odd indices goes into ODD, even indices go into EVEN. You want to answer this question:

  "How many ways are there to fill in -1, so that no adjacent numbers are the same"

  Solve that question for the two arrays, final answer is simply solve(EVEN)*solve(ODD)

• 3 years ago, # ^ |

  Great observation!

• 2 years ago, # ^ |

  can u please give some mathematical proof of C.. that is why we sort on the basis of beauty.. in my opinion if we multiply beauty and length and then sort is it work???.... plz help me?? I can't understand...Thanks

• 13 months ago, # ^ |

  Can you explain more how it will not cause an error?

• 49 minutes ago, # ^ |

  How did you get the formula n(n+1)?

• 3 years ago, # ^ |

  ← Rev. 2 →  

  0

  1. First we need to find the shortest path between nodes of the form 2i−12i−1 to 2i2i. This can be done with a dp on the tree. Notice that any such shortest path will only take one edge between the even tree and the odd tree. Simply replacing the cross edge distance will not change shortest distances, and will make reasoning through the problem easier.

  2. Next to find shortest paths, if you use centroid decomposition we can find shortest path from root to a node by:

  • dp[i][j] defined to be the length of the shortest path from node 2i−j2i−j to the root with another tree dp.

  If you use binary jumping, you can use: - dp[i][j][k][l] defined to be the the distance from 2i−j2i−j to the 2l2l th ancestor in either the even or odd tree (kept track of by k).

  I personally find binary jumping easier. Either way, this uses the critical observation that if you want to find the path from one node to another, you need to pass through the simple path on the tree between the two nodes (possibly jumping back and forth between the trees).

• 3 years ago, # ^ |

  cntSame(0) = 0 since there is no way to make 'aa' have all pairs of consecutive elements are distinct. cntDiff(0) = 1 since there is one way to make 'ab' have all pairs of consecutive elements are distinct.

• 3 years ago, # ^ |

  Sorry to bother you, could you explain how did you get that recurrence on problem E? I'm having trouble on find it.

  • 3 years ago, # ^ |

    theProcess Consider a -1 -1 ...ltimes... -1 -1 b

    You need to find the no. of arrays in which no two consecutive elements are equal.

    So first if you assign the value to the lth "-1" element i.e. element before b, obviously you can assign all the values to it from 1 to k, except b. You can't assign b to it because no two consecutive elements should be equal. So there are (k-1) ways in which you can assign the value to lth "-1" element.

    Now I hope you know the meaning of cntSame(l), and cntDiff(l).

    To calculate cntSame(l), consider what happens when a=b.

    Suppose you assign value to p to the lth "-1" element. Obviously, p!=b.

    Since a=b, therefore p!=a. So, remaining number of values will be (k-1) i.e. except a(or b, since a=b). Therefore cntSame(l) = (k-1)*cntDiff(l-1)

    To calculate cntDiff(l), consider what happens when a!=b.

    Suppose you assign value to p to the lth "-1" element. Obviously, p!=b.

    Since a!=b, You can either assign p=a or p!=a. There will be exactly one case to assign p=a and (k-2) cases to assign p!=a. (k-2 because you cannot also assign p=b)

    Therefore cntDiff(l) = cntSame(l-1) + (k-2)*cntDiff(l-1)

• 3 years ago, # ^ |

  Hi, In problem E, why do we need to look into the two different cases of sequences possible .i.e., a -1 -1 ... -1 b , a==b and a!= b ? Can we not simply iterate through the elements and whenever there is a -1 , it can take either k-1 values (if the next element is -1) or k-2 values(if the next element != -1). Why wouldn't this work ? Thank you :)

• 3 years ago, # ^ |

  https://codeforces.com/contest/1140/submission/52462663

  yes the length of the i'th one must be included.

  so the idea is to consider every i'th element as the minimum beauty. for this we sort the songs in descending order of beauty. so the first song we consider will have the highest beauty. (what if 2 songs have same beauty? read last 2 para)

  we will at all times try to maintain a list of songs of size at most k. this list will contain at most k songs with the highest length, not including the current i'th song. so if we already have a list of size k, then we remove the song with the smallest length. so size become k-1. then we include the current song into the list, size becomes k, and update our maxTillNow. if out list is less than k, then we just simply include the song and update maxTillNow.

  to maintain this list we will use a priority_queue (min heap), where the top element is the song with the smallest length. this way we don't need to keep track of song indexes.

  while sorting our list of songs in descending order of beauty, if 2 songs have the same beauty we place the song with the smaller length first (this is very important). this is because when we consider the i'th beauty, obviously the i'th length must also be included. which means, if there is already a song in the list with the same beauty as our current minimum beauty we need to pick the one with the smaller length to discard.

  this process becomes easier to deal with for 2 or more songs with same beauty, if we consider the song with the greater length as late as possible. because the song with the smaller length will already be in the list, so we can simply discard it and include the current song.

  read code for more clarity.

• 3 years ago, # ^ |

  only 1 time loop will execute for each outer loop. So we could have used if condition (instead of iterating over set) as well because at a time, its gauranteed, set size can only be 'k' at max, since we are increasing set size by 1 in each outer loop iteations.

• 3 years ago, # ^ |

  You may remove some characters from the string before applying the operations.

  • 3 years ago, # ^ |

    Oh,thank you very much

    • 5 months ago, # ^ |

      ← Rev. 2 →  

      0

      hi!can you tell me if string is "<<<<>>>>",then why the answer is 4 and not 1?

  • 3 years ago, # ^ |

    In problem C,I cannot understand why the does the set use pair<int,int> instead of int .In other words,if I submit my code with set 《int》 ,then I will wrong on test 3 .It seems that we haven't utilize the second of the pair<int,int>. Sorry for my poor English.

    • 3 years ago, # ^ |

      Set does not contain duplicate elements. but we need to store it. pair<int,int> is used for this reason. Because index itself is stored with the beauty value, there is no chance for duplicate elements.

      • 3 years ago, # ^ |

        Oh,I understand.Thank you for solving my problem.

• 15 months ago, # ^ |

  Set does not contain duplicate elements. but we need to store it. pair<int,int> is used for this reason. Because index itself is stored with the beauty value, there is no chance for duplicate elements.(copied)

  • 15 months ago, # ^ |

    Thanks man