SRM 613: The doubt

Third python SRM, this time I am not sure if the solution for div1 500 is doable in python, but I was very far from figuring it out so maybe the solution is actually quite fast.

Div1 250: cats

There are many cats in the horizontal axis. You know their integral positions. Each cat has to move exactly `M` units left or `M` units right. Find the minimum gap between left-most and right-most cat possible after a single move. Positions are between -100000000 and 100000000

I will find it hard to explain it editorial-style, because it is rather obvious that there should be a pattern like RRRR...LLLL, such that some cats on the left side of this pattern move right and the rest move left. There are only `O(n)` of these patterns so we can try them all.

My way of acquiring those patterns was to pick a position and tell cats to move towards that position. It passed examples, and submitted quite fast (I think it is because of python's shortness of code), then I noticed a potential bug. If I tell a cat to move towards itself, then it will always pick the left side (I used <= operator) instead of maybe trying the right side. So for a while I wondered if there is a case in which the cat in question needs to move to the other direction. I eventually found that 's not the case. You don't need to try both LLLLLLLL...LL and RRRRRRRRRR...R, because the end result will be the same. So I thankfully avoided a needless resubmission penalty.

class TaroFriends:
 def getNumber(self, X, T):
    def towards(z,x):
        return z + T if z <= x else z - T 
    
    def allTowards(x):
        l = [ towards(z, x) for z in X ]
        return max(l) - min(l) 
        
    return min( allTowards(x) for x in X)

Python seems to be making me trend towards functional-ish programming. Would you take a look how beautiful this code is? I checked out other people's codes and they are awful :)

Div1 500: GCD madness

So we should pick `N` numbers such that each number is between two bounds and the GCD of all the picked numbers is `K`. All the numbers in the input are between 1 and 10^9. Have fun

I didn't really do much.

The maximum number of distinct prime factors of `K` is 9, because the product of the first 10 prime numbers is larger than 10^9. So maybe if we focus on the prime factors... Each picked number must be a multiple of `p^r` if `p` is a prime factor of `K` and `r` its exponent in the factorization. Also, `r` should be the minimum exponent of this prime number for all the `N` numbers. Besides of this I didn't have much luck.

I initially made a huge mistake, thought `N` was up to 50, so I was coding some dynamic programming (which still had complicated parts like having to count numbers that are multiples of something but not multiples of a list of other numbers). When I figured this was completely wrong, I had tons of code and the match was ending, so I submitted it for challenge phase fun. Too bad the code was challenged very fast.

So

When python works, it works, It has been a while since I had such a relatively high score in div1 easy. It was all because of python's potential for concise code.