Something like Berland State University and some other common names.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Something like Berland State University and some other common names.
In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
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
I think it would be better if Codeforces shows contest performance rating with rating change like Atcoder.
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?
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.
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)?
problem
I am not getting any idea about this one. Please help.
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?
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.
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.
Name |
---|