### it_is_not_an_alt's blog

By it_is_not_an_alt, history, 3 weeks ago,

problem link 339C - Xenia and Weights

The editorial of this problem tells us to make a graph of nodes where each node is a tuple (i,j,k). And after making this node we have to find a path from (0,0,1) to some node (x,y,m). Now according to the question, this graph is acyclic and directed. And each node can have 9 outdegree (there are 10 weights to select from but we cant select the previous weight). And the length of the path is m<=1000. Now i cant find a way to find the path from (0,0,1) to (x,y,m). Because i think there can be 9^(1000) possible paths. How to prove that the number of paths we have to check will actually be less so that we dont get a TLE. Please Help!!

• +23

By it_is_not_an_alt, history, 2 months ago,

Can you guys share some programming competitions that are open for all? i.e it is not necessary to be a college student to participate in them. I just want to know because I dont want to give up CP after college I want to continue after college also.
So i found out that google code jam doesn't require the participant to be a college student. And also Facebook hacker cup. Can you list some more?

• -9

By it_is_not_an_alt, history, 3 months ago,

Suppose we have 2 arrays of size n (say A and B) and we have to select k indices i1,i2,i3....ik, such that all are valid indices (i.e all belong to [0,n-1) ) .And let valA = $\sum_{j=1}^{k} A_{ij}$ and let valB = $\sum_{j=1}^{k} B_{ij}$. Then min(valA,valB) should be maximum. How to solve this? I tried using dp but couldnt figure out how to move from dp[i-1] to dp[i].
Is there any other way to think about it?

• +5

By it_is_not_an_alt, history, 3 months ago,