hossainzarif's blog

By hossainzarif, history, 2 months ago,

Problem
I got this idea. $dp[i][j]$ be the number of ways to divide j people with the group of size $A$ to size $j$.
$dp[i][0] = 1$ and $dp[i][j] = dp[i - 1][j] + \sum\limits_{k = C}^D\binom{j}{k * i} * dp[i - 1][j - k * i] * \dfrac{(k * i)!} {(i!)^k * k!}$
This has a complexity of $O(n^3logn)$ which won't pass. How to improve it to $O(n^2logn)$ or $O(n^2)$
code

• 0

By hossainzarif, 2 months ago,

I think it would be better if Codeforces shows contest performance rating with rating change like Atcoder.

• +46

By hossainzarif, 3 months ago,

problem
I tried this problem with dijkastra using state graph $(city, silver coin)$ . But, I could not get any way without updating through every edge which would obviously result in TLE. Then, I think let's update with two kind of edge.
$1.$ $(city, silver coin)$ to $(city2, silver coin - cost[city][city2])$ where $cost[city][city2]$ is the silver coins needed to go to $city2$ from $city$.
$2.$ $(city, silver coin)$ to $(city, silver coin + c[city])$
And it worked. But, why this works?

• +1

By hossainzarif, 3 months ago,

problem
submission
I don't know why my approach works.
I first found out the balance of every string $(number of left bracket - number of right bracket)$ and minimum balance of every string. let $bal$ be balance and $mnbal$ be minimum balance. Like $()))(($ has balance $0$ and minimum balance $-2$ (obtained at index $3$).
Then I took 4 vectors.
$v_1$ having pair $(mnbal, bal)$ where $mnbal >= 0$ and $bal >= 0$
$v_2$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal >= 0$
$v_4$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal < 0$ and $mnbal = bal$
$v_3$ having pair $(mnbal, bal)$ where $mnbal < 0$ and $bal < 0$ and $mnbal \neq bal$

Then, I sorted $v2$ in decreasing order and $v3$ in increasing order, and appended $v_1$, $v_2$, $v_3$, $v_4$ in order checking conditions and it got accepted. But, I can't find out why my idea works.

• -3

By hossainzarif, history, 3 months ago,

I have been trying to solve atcoder problems recently using this problem filter website.
website
However, I am generally finding blue tagged problems more challenging than 1900-2000 rated codeforces problems. I am even finding some cyan coloured problems challenging enough, more challenging than 1700-1800 rated CF problems. Is this only me or others also facing this?
What are the rating of problems based on colours(unfilled, half-filled, filled)?

• +17

By hossainzarif, history, 3 months ago,

problem

• 0

By hossainzarif, 3 months ago,

There are so many online judges right now. So many contests happened. How do the problem setters get new problems so frequently and how come the ideas of that problem don't appear in some other problems?
And how do the problem setters check that there problem is unique?

• +7

By hossainzarif, history, 5 months ago,

I am currently solving 1700-2000 rated problems. But, looks like it isn't helping me cause I end up going to editorial 50% of the time. I am also having trouble with dynamic programming problems. Solved around 20 dp problems and still facing difficulties finding the states and transitions.

What would be the strategy of my practice?? Help please.

• +77

By hossainzarif, history, 6 months ago,

https://vjudge.net/problem/LightOJ-1289
This problem states to find lcm from 1 to n. I firstly did sieve from 1 to 100000000. Then, calculated the multiple results of all prime powers which does not exceed x (2 <= x <= 100000000). And then processed the query.
https://ideone.com/1zDXDc
I tried out every possible cases I found and don't see any RTE in my compiler. Even for this case in the Ideone.