hossainzarif's blog

By hossainzarif, history, 3 years ago, In English

Something like Berland State University and some other common names.

Full text and comments »

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

By hossainzarif, history, 3 years ago, In English

In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.

Full text and comments »

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

By hossainzarif, history, 4 years ago, In English

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

Full text and comments »

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

By hossainzarif, 4 years ago, In English

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

Full text and comments »

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

By hossainzarif, 4 years ago, In English

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?

Full text and comments »

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

By hossainzarif, 4 years ago, In English

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.
Please help.

Full text and comments »

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

By hossainzarif, history, 4 years ago, In English

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)?

Full text and comments »

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

By hossainzarif, history, 4 years ago, In English

problem
I am not getting any idea about this one. Please help.

Full text and comments »

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

By hossainzarif, 4 years ago, In English

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?

Full text and comments »

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

By hossainzarif, history, 4 years ago, In English

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.

Full text and comments »

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

By hossainzarif, history, 4 years ago, In English

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.

Full text and comments »

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