Codeforces Educational 161 div2

Codeforces Educational 161 div2

 

 

Problem A

Standard difficulty for problem A.  This one you can trick yourself easily though and comprehending what it is asking is a little challenging.  The template is only invalidated if it fails at all i,  if it passes at any ith index it is good.

 

Check the following.

 

1.         if all(a[i] == c[i] or b[i] == c[i] for i in range(n)):

2.                print("NO")

 

 

Problem B

Hard for a second problem, requires basic combinatorics and mathematics.

Sum of the two smallest sides has to be less than the longest side.

Triangle Inequality Theorem, logic to figure out that their are only few possibilities.

 

But also you need to know how to pick 3 items from a collection of distinct items. And how to pick 2.  They are binomial coefficient from combinatorics.  And they are easy to compute for 3 and 2 with the formula n * (n - 1) * (n - 2) // 6 for example.

 



 

Problem C

Easy for problem C it is just a prefix sum.

If you read the problem a second time, it may become obvious that it is not as difficult as it looks.  There isn't any graph theory necessary for this.  All you have to do is calculate prefix and suffix sum.  Use prefix sum for when traveling to larger node and suffix sum for when traveling to smaller node.  And just calculate the sums based on the rule it gives in the problem.  Make sure if it is a path that is smaller it is just cost 1 coin.

 

Problem D

You can apply doubly linked list for O(1) deletion of monster while also keeping the order of the monsters in the array.  Then you just need to iterate over the rounds with the doubly linked list.

 

It is a fun practice of using doubly linked list data structure.

 

Problem E

 

This problem can be solved by noticing something about the binary representation of the X.  You can use that to solve the problem.  You basically want to match the bitmask of it,  cause if you add the 0 integer to the end of the subsequence you can make x + 1.  Or you can add the largest integer to the end of the subsequence you can make 2 * x.

 

So then you can get the answer by a combination of x + 1 and 2 * x to get the correct answer, cause any integer can be composed of this. 

 

You actually just need to look at the binary representation of the X.  And then just loop through it from MSB to LSB and always multiply by 2.  But sometimes you add 1, whenever you see a 1.  You skip the first 1 because it is for the empty subsequence.  For the rest you just follow this and it works.  By adding the 0 or largest integer to the end of the array.  You can get exactly X increasing subsequences.

 

Problem F

The problem is asking for you to find the minimum number of operations

so that you have all elements in the sequence are the same.  The constraint on x is less than or equal to 100.  You can take any l, r subsegment and change all values to some k where k is less than or equal to x.  And k cannot exist in that subsegment.  So you can change all the elements to a value that doesn't appear in that subsegment. 


Recognizing it is a interval dp problem is easy.  And you have states (l, r, k). The transition is tricky though. I divide the transitions into segment splitting and transformation below. 

 

Now you can suppose you can merge two of these where it already has minimum number of operations to get all elements equal to k.  That means you are treating that entire range as a single element.

You have an element which represents a segment with a specific element value and it has the minimum number of operations to achieve that state.

 

This is my question.

  How would I come up with two precomputation tables that rely on each other?


Complicated dynamic programming problem because you need to precompute the min operations to assign all elements to k in an interval [l,r] and you need to precompute the min operations to remove all occurrences of k from an interval [l,r].  And these both depend on each other?  That is you can precompute one from the other (and vice versa).

 

You can always transform the min operations to remove all occurrences of k from an interval [l,r] into min operations to assign all elements to k in the interval [l,r].  That is a valid operation.

 

But you can also transform the min operations to assign all elements to m in an interval [l,r] into the min operations to remove all occurrences of k from the interval[l,r].  where k != m

 

What is the problem, you have a cyclic dependency right?

dp(l,r,k) depends on dp2(l,r,k)

dp2(l,r,k) depends on dp(l,r,m) m != k

dp(l,r,m) depends on dp2(l,r,m)

dp2(l,r,m) depends on dp(l,r,k)

 

so the cyclic dependency is that dp(l,r,k) depends on dp2(l,r,k), but also indirectly dp2(l,r,k) depends on dp(l,r,k). 

 

segment splitting, you can split into two segments and take the min operations to get those segments to be equal to k, and just add those to the answer for here.  So suppose you split at i

then you take dp(l,r,k) = dp(l,i,k) + dp(i + 1, r, k) It is the sum of min operations for both of those segments.

Direct Transformation, you can change all elements into k if you take from a segment dp2(l,r,k), where for the interval [l,r] there is no k.  All elements don't equal to k.  You can take that and transform that segment into dp(l,r,k) = dp2(l,r,k) + 1, perform one operation to change all elements to k

 

You can do this but you need to calculate dp2(l,r,k) which is min operations to remove all occurrences of k.

 

segment splitting, you can slit into two segments and find the min operations to get those segments to remove all occurrences of k.  So that would be dp2(l,r,k) = dp2(l,i,k) + dp2(i+1,r,k)

Direct Transformation, removing all occurrences of k is equivalent to setting all the occurrences to m, where m does not equal k.  So you could say dp2(l,r,k) = dp(l,r,m).  


 

 

Comments

Post a Comment

Popular posts from this blog

Codeforces Round 918 div4

Image
  Codeforces Round 918 (div 4)   Problem A Use the frequency to determine the element that appears once.   Problem B Have a set for each row and column with "ABC" and remove characters in specific (r, c) pairs. And there will remain a single set with just one character.     Problem C Determine if the sum is a squared integer.   Can use math.sqrt to determine this.   Problem D Create string of C and V for identifying the consonants and vowels. create a deque to store the locations of dots. Iterate over the CV string, and anytime you find CC, that means it must be CVC was the prior syllable.   Cause you found a CVCCXXX,   The other pattern that can appear is if XCVCVX,   if you see VCV, that means there must be a CVCVX,   You know there was a CV pattern before the CV of most recent.   Which the most recent could be a CVC, you don't know what X is ...
Read more

Algorithm: Digit DP

Image
  Algorithm: Digit DP    Solutions to some problems that can be solved with Digit DP algorithm. Digit Sum   The problem is asking to find the count of integers in the range from 1 to K (inclusive) such that the sum of digits is divisible by D.   Do you want to exclude zeros? If the answer is yes than you need to track which states do not contain a nonzero digit yet.   Why do I want to exclude zeros, because 0 % 1 = 0 in python, so it says 0 is divisible by 1 or actually any positive integer.   So we have one part we will track which is the "zero"   Do you want separate logic for tight bounds? Yes you want to make sure you have separate logic for when the prefix is exactly equal to K.   This way it doesn't allow any numbers greater than K.   So we have another part "tight"   Of course we need to track at what index we are when iterating through the digits. So we have an "index" ...
Read more

Codeforces Round 920 div3

Image
  Codeforces Round 920 (div 3)     Problem F Square root trick, You can use the square root trick to calculate prefix sums in n * sqrt(n).  Where you compute the prefix sums for each step size from 1 to sqrt(n).  Now anytime you have a query where d <= sqrt(n) it can be solved in O(1) with the precomputed prefix sum.  Else it will have sqrt(n) iterations in brute force looping through to get the value.   You do need two prefix sums because you have to create the ones that will give the answer for this specific problem.  Which is a little bit tricky to derive.  Problem G   My approach was very bad for this problem.   You want to use a diagonal prefix sum and column-wise prefix sum.   But the thing is that implementation is very important.   If you try to pad by K to avoid where the diagonal is out of bounds you will end up with 10^5 by 10^5 matrix which is too large.   And if you pad by 1 for the diagonal ...
Read more