### Bekh's blog

By Bekh, history, 3 weeks ago, ,

Hello,

I was trying to solve 383E - Vowels. Using the technique described here: https://codeforces.com/blog/entry/45223

I managed to get AC here: 61233188 using regular memory reduction (Reducing one of the dimensions to the size of 2).
I don't understand how it can be reduced to one-dimensional like this: 61233599.

Here is an image (with my amazing paint skills :P) to demonstrate my understanding of the dp dependencies in this problem:

I can't see how these updates are done in the solution with only one dimension.

Any help would be appreciated.
Thanks.

• +3

By Bekh, history, 6 weeks ago, ,

Hello,

I have been trying solving this problem: 1747 — Swap Space

Here is my WA code: https://ideone.com/64kU5M

I think the issue is with my comparator since I've seen solutions with other comparators that get AC like this one: https://github.com/morris821028/UVa/blob/master/volume017/1747%20-%20Swap%20Space.cpp

The idea behind my comparator is: if there are 2 disks to be reformatted $X$ and $Y$ and I have available storage $S$. Then if I take $X$ before $Y$

$S$ must be >= $X.A$ and $S + X.B - X.A$ >= $Y.A$, with rearragement:
$S >= max(X.A, Y.A - X.B + X.A)$

Similarly if i take $Y$ before $X$
$S >= max(Y.A, X.A - Y.B + Y.A)$

thus my comparator between $X$ and $Y$ is like this

bool cmp(pair<long long, long long> x, pair<long long, long long> y)
{
return max(x.first, x.first + y.first - x.second) < max(y.first, x.first + y.first - y.second);
}


Could somebody tell me what's wrong with my comparator?

Thanks.

• +8

By Bekh, history, 2 months ago, ,

Hello,

I was trying to solve 1117D - Magic Gems using Matrix Exponentiation. I'm trying to use an implementation (It was moriss821028's if I recall correctly) for Matrix Power since it's much faster than mine. I'm using 2 transformation matrices and multiply them to get the final transformation matrix named transform and then raise it to the power of n.

This submission: 58207232 gets AC, while on my machine it gives segmentation fault on line: 108, the line where I raise the transform matrix to the power of n. Following it with the debugger, it doesn't enter the operator ^ function at all, it stops on the definition line and halts.

Reducing the dimensions of the array v to 180 x 180 seems to fix the issue locally but the code doesn't seem to take that much memory. Idk if this is related to a memory leak or what.

My IDE is CLion, the compiler is MinGW version 5.0, my CMake version is 3.13.2, and I'm using C++ 14.
It prints exit message Process finished with exit code -1073741571 (0xC00000FD).

Any help would be appreciated

• +7

By Bekh, history, 4 months ago, ,

Hi,

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?

• -2

By Bekh, history, 4 months ago, ,

Hello,

In problem: 233B - Non-square Equation
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.

• +8

By Bekh, history, 8 months ago, ,

Hello,

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)

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?

• +5

By Bekh, history, 14 months ago, ,

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.

• +5

By Bekh, history, 14 months ago, ,

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]