programming_monthly

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. ...

  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" ...

  ABC 335     Problem C This is a fun puzzle, cause once you make the connection it feels great.   You need to make the connection that when the dragon moves, you just append new position of head, and then all of the other positions move one forward, so just look at bottom N element sin the stack.   So you just look at the position p from the back of the stack to get where that current segment of the dragon is in the coordinate space. Problem D I think this is a little obvious, just take the spiral.   Implementing the spiral to fill in the values is the only tedious aspect. Problem E The easy approach to this problem is to observe that it is not a DAG.   But you can merge adjacent nodes that have the same value with union find or dfs.   And have those act as a connected component and it is now a supernode.   Then this will create a DAG and now you can perform DP on it.   Cause you need DP to find the maximum num...