Friday, March 21, 2014

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.


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.


vexorian said...

Being totally honest, I still have doubts about my div1 250.

I ran code through random numbers but I didn't find anything wrong.

But still.

Karan Dhamele said...

" it is rather obvious that there should be a pattern like RRRR...LLLL " can you please explain the obvious ?

vexorian said...

hmnn that's the problem, when something seems obvious it is harder to explain.

But, since we want to minimize the distance between the right-most and left-most point, then we can prove that the directions of the left-most and right-most point cannot be LR (left-most moves left, right-most moves right). Maybe a solution can have LL, RR or RL. Anyway, you used LR, the distance between these two points will forcefully increase, but you can just use LL or RR and the distance will stay the same. So it follows that for every pair of indexes i < j, then d[i],d[j] cannot be LR. From this we can show the pattern cannot be anything other than RRR...L...L