amr0's blog

By amr0, history, 4 years ago, In English

Hello Codeforces! I was trying to solve https://codeforces.net/gym/102920/problem/L using divide and conquer. To get the solution that crosses the midpoint I use the observation that the left endpoint, at index i, will be in a monotonically increasing sequence and the right endpoint, at index j, will be in a monotonically decreasing sequence but I get TLE. This is a code snippet from the code I submitted: https://ideone.com/pRWLDD . Your help is appreciated

Full text and comments »

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

By amr0, history, 4 years ago, In English

Hello Codeforcians, I tried to do the famous "coins in a line problem" where two players play a game in which at each turn a player can select one coin from one end of the line of coins (the coins are sorted in a row). The problem then is to determine the guaranteed profit player A can make assuming player A starts first. The coins' values are $$$v_0$$$ to $$$v_{n-1}$$$. My approach was to apply for the recursive DP formula is:

F(i,j) = Max(pref(j)- pref(i) — F(i+1,j)+values(i), F(j-1)-pref(i-1) — F(i,j-1)+values(j))

where pref[i] is the prefix sum of all the coin values $$$v_0$$$ to $$$v_i$$$

However, the DP I found online is F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), Vj + min(F(i+1, j-1), F(i, j-2) ))

Can anyone tell me why approach is wrong?

Thank you

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By amr0, history, 5 years ago, In English

Hello Codeforcians!

I would like to know if there is an efficient method to calculate

$$$ \sum_{k_A+k_B+k_O+k_R=k}{N\choose A+k_A,B+k_B,O+k_O,R+k_R} $$$

where $$$k = N-(A+B+O+R)$$$ (of course all k's are greater than or equal zero), the output is modulo $$$1'000'000'007$$$, and $$$0\leq A,B,O,R, N\leq 400,000$$$. The time limit was 2 seconds, however any suggestions are more than welcome.

Thank you!

Full text and comments »

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

By amr0, history, 6 years ago, In English

Hello, I am not sure how to solve this problem on graphs from a previous contest. Any help is appreciated.

https://codeforces.net/predownloaded/49/4e/494ef6d6376342a0bdbd9e42cb0f57389fe21d3b.png /predownloaded/49/4e/494ef6d6376342a0bdbd9e42cb0f57389fe21d3b.png

Full text and comments »

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