Bekh's blog

By Bekh, history, 3 weeks ago, In English,

Hi,

The Problem

AC Code (2.5s): 56017075 (Or here if you can't view gym submissions)
TLE (over 30s, tested on custom private group contest with custom TL): 56017081 (Or here)

Regardless of the problem and its solution, the ONLY line that changes between the 2 submissions is the way I check if the state was calculated before or not. When I check it using if (ret != -1) it gives TLE, but when I check it using visit array is (visit[i][j] == vid) it passes. I don't even remove the extra memset for memoization array in each testcase when using the visit array. Why would this very small change result in that huge difference in time?

Read more »

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

By Bekh, history, 6 weeks ago, In English,

Hello,

In problem: 233B - Неквадратное уравнение
I was wondering why in submissions like this 12604154 it is sufficient to only check a small range around the square root of n. How can I deduct something like this from the equation, and how to prove it?

Thanks.

Update: Here's a formulation that helped me understand it, maybe it'll be useful for someone.

The main equation is: $$$X^2 + X * S(X) = N$$$

Let $$$Y = X + S(X)$$$.
$$$Y^2 = X^2 + 2 * X * S(X) + {(S(X))}^2$$$ $$$Thus$$$
$$$Y^2 >= X^2 + X * S(X)$$$

Since $$$X^2 + X * S(X) = N$$$ then
$$$Y^2 >= N$$$
$$${(X + S(X))}^2 >= N$$$
$$$X + S(X) >= sqrt(N)$$$

$$$X >= sqrt(N) - S(X)$$$

Also, check mohamedeltair's comment for a general proof for the upper bound.

Read more »

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

By Bekh, history, 5 months ago, In English,

Hello,

Here's the problem link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1159

I know and already got AC with other neater solutions, but I was trying various dp states/approaches for practice. I wanted to know what I am missing in this dp approach since I'm getting a bit lower value than the sample output (0.5012511 instead of 0.5002286)

Solution link: https://ideone.com/AjdoVF

approach:

  • i is zero based

Dp definition:

  • dp[i][rem] is probability to get a final even 'usedCandy' count in range [i, m) using 'rem' candies such that usedCandy = totalCandies — rem

base case:

  • at i == m, return isEven(usedCandy)

transition:

  • at each [i][rem], if 'tk' is amount given to man 'i'. 'tk' is in [0, rem]

  • answer = Summation for all 'tk' in [0, rem] -> P(man 'i' getting exactly tk candies) * dp[i + 1][rem — tk]

  • P(a man getting exactly 'tk' candies) having 'rem' candies in total can be found through binomial theorom C[rem][tk] * p^tk q^(rem — tk) such that p is probability for

  • a person to get a single candy = 1/(m+w) and q = 1 — p

If something is not clear with my solution, please ask. Where am I going wrong with this dp?

Read more »

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

By Bekh, history, 11 months ago, In English,

Here's the problem : 227C - Flying Saucer Segments

In the editorial here: http://codeforces.com/blog/entry/5378?locale=en We ended up having F(n) = 3*(F(n-1) + 1) — 1 Could somebody please elaborate on how to get we got ((3^n) — 1) from the recurrence? Sorry if this is a newbie question I'm trying to learn more on the topic.

Read more »

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

By Bekh, history, 11 months ago, In English,

http://codeforces.com/blog/entry/14256 in D2-C.

I understood that for each x there is exactly 1 k. But how can I prove that for each K in [1, a] there always exists nice numbers for all remainders [1, b-1]? For instance if a = 3, b = 5. How to be so sure that for Each k {1, 2, 3} there will always be nice numbers with remainder values [1, b-1]

Read more »

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