Something like **Berland State University** and some other common names.

Before contest

Codeforces Round (Div. 1, based on COMPFEST 15 - Final Round)

4 days

Register now »

Codeforces Round (Div. 1, based on COMPFEST 15 - Final Round)

4 days

Register now »

*has extra registration

Before contest

Codeforces Round (Div. 2, based on COMPFEST 15 - Final Round)

4 days

Register now »

Codeforces Round (Div. 2, based on COMPFEST 15 - Final Round)

4 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3775 |

2 | Benq | 3724 |

3 | orzdevinwang | 3697 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | cnnfls_csy | 3620 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 163 |

5 | maroonrk | 162 |

6 | SecondThread | 159 |

7 | nor | 158 |

8 | -is-this-fft- | 153 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

Something like **Berland State University** and some other common names.

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

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.

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.

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/04/2023 15:38:29 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|