ABC 336

 

ABC 336

 

 

Problem C

You can only allow integers [0,2,4,6,8]  That is 5 integers.  If you write down the example 0,2,4,6,8,20,22,24,26,28,40. 

You can realize that you can basically convert an integer to it's base 5 representation.  For example

0 is 0

1 is 1

2 is 2

3 is 3

4 is 4

5 is 10 => 20

6 is 11 => 22

10 is 20 => 40

 

That is the translation into a base 5 representation gives the corresponding index into the 5 integers that are being used.

Problem D

Nice dynamic programming practice problem.

The idea is to calculate the largest the peak you can get from scanning backwards initially.  You know that the next peak can only be one greater than the previous peak.  So you just add one and take the min with the actual array value.

Then you need to move in the forward direction and pick only the ones that work, which are the min of the peaks from the forward and backward direction.

 

Problem E

 

  1. Fix the digit sum at most there is 1 to 126 for the digit sum
  2. Up to some integer you want to find how many good integers there are, where a good integer just means the integer is divisible by the sum of digits.
  3. Now if you fix the digit sum can you solve it that way.  So now I'm only considering integers that have digit sum equal to some fixed s value.
  4. Then for each integer you only have to store what that integers remainder is when divided by s.  And then at the end you will include in your answers for the solutions that contain a total digit sum equal to s and those with remainder = 0.

 




 

In other words you simplify the problem.  You say can I solve this for a specific digit sum s.

And you can if you keep track of the states in the bag (digit sum, remainder modulo s, tight)

 

new_remainder = (remainder * 10 + dig) % s

 

Problem F

not solved

Problem G

not solved

 

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