it_is_not_an_alt's blog

By it_is_not_an_alt, history, 3 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By it_is_not_an_alt, history, 2 months ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

By it_is_not_an_alt, history, 3 months ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By it_is_not_an_alt, history, 3 months ago, In English

Problem link — https://codeforces.com/problemset/problem/1355/D

I was able to prove that if S>=2*n, then Petya can always win (same logic which is given in the tutorial). But I am not able to prove that if S<2*n then Petya will always lose. How to prove that?

Read more »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it