Bekh's blog

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

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: Untitled.png

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

Any help would be appreciated.
Thanks.

Read more »

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

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

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.

Read more »

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

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

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).
If there is any more information you need, please ask. I'm a kind of a newbie when it comes to these stuff.

Any help would be appreciated

Read more »

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

By Bekh, history, 4 months 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, 4 months ago, In English,

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.

Read more »

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

By Bekh, history, 8 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, 14 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, 14 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