Why do you want unrated round when there are so many virtual contests already?

Why do you want unrated? The whole point of rating is to see if you are improving or not, and unrated rounds would also be not fun. If you want unrated just do virtual participation

Oh I will downvote your comment buddy.

Good luck! But don't get too focused on this, or you will become nervous and won't solve problems that well. Remember, it's just a round and you should try to enjoy it no matter what your rating now is:)

I try to aim for X + 400, I think it doesn't matter much

I agree

I prefer segment rather than single rating. I train on problems rated from x to x+500 where x is my rating.

Start with problem rating range 800-1000 and after every solve, increase the lower bound and upper bound by 300. In this way, you can practice fast solve and hard solve both.

Are u making the same kind of comments from different parallel universes ? °_0

You just have to believe that you can do it.

It's called educational for a reason

Thanks, good luck to you too

Fine, AB is already enough to me

Good luck!

well next time then

It really is.

lol fr. It was super implementation heavy so hacks are gonna be brutal :(

Agree, but again C was harder than D... and gap between B and D isn't big.

yes

c and d >= 1900 (acc to me)

Yeah, if you solve just 3 problems you get in top-1000, C is very cringy, D is hard to optimise (had to use pragmas)

I agree with u.(very very

Little clearer: Don't judge by this contest and don't leave codeforces

But every 1 in 4 contest is like this only.

it may be not. Actually when you check the solution you won't find it so difficult :)

As an Expert you shouldn't say that Hhh

Mind Blowing problems.

It's a contest where there's a large gap between two adjacent problems (In this case B and C). This leads to a bottleneck where a lot of people can't get past that one question, meaning the rankings for them are solely determined by the SPEED in which they solved the other problems.

but literally how do you hack A or B

like, how the heck

Glad to see that greys are well-acquainted with what Div. 1 is like.

Yeah, I tried dp but it was too slow.

Not entirely sure what you mean by space optimization, but I used DP with $$$n$$$ columns and 2 rows (representing many more rows, but only the previous row is needed for filling the current row), along with keeping track of when the first non-zero element of the column will be (so I don't waste time iterating over the elements before it).

This does sound like I'm saving space, so it might fall under space optimization DP (again, idk what you actually mean by it), but my main objective was to save time.

It's not very hard (it just suck that I didn't implement this on time).

Edit: When the test cases got updated, I got TLE, then I resubmitted the code, then got AC. I guess because the constraint was so tight that it just comes down to being lucky :<< (My solution ran in 1949ms, very close to the constraint of 2000ms).

Code (failed): 167051557. Code (passed): 167085973

bro im so agree with you

No contest is "too difficult" everyone is in the same conditions than you, so if you are better than then, no matter how difficult the contest is you are gonna raise your rating

There is only a fairly simple pattern of movement possible, because each cell must not be entered more than once.

This is, we go right covering both rows until some col, then got right in the current row to the end, then left back to the col in the other row.

All of this can be precalculated with prefix sums, and min/max operations.

Of course all of this is very off-by-one error prone. And actually, I am still not sure about the meaning of:

"The robot can only move into a cell (i,j) if at least ai,j seconds have passed before the move."

If a[i][j]==x, can we enter at x, or at x+1?

First I wrote a $$$O(\sqrt{n} \cdot n \cdot \log n)$$$ DP, thinking it may pass, but it's TLE. Then I realized there is an optimization to get rid of the $$$\log n$$$ part.

We can calculate $$$dp[i][j]$$$ — number of way to get $$$j$$$ in $$$i$$$ moves. Then for $$$x = 1$$$ $$$dp[1][j] = 1, dp[2][j] = dp[1][j - 2] + dp[1][j - 4] + dp[1][j - 6] + \dots, dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - 2i] + \dots, dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]$$$ (try to understand, why last correct). This is a quadratic dp. But look: if we done $$$i$$$ move, our answer is at least $$$1 + 2 + \dots + i = O(i^2)$$$. This means, that the first dimension of array is $$$O(\sqrt{n})$$$. I brough 800. Also, if you try to declare the whole array, you will get $$$MLE$$$. Instead, declare only two rows, calculate next, and delete previous.

I used DP, where $$$dp[i][j]$$$ represents the number of ways to reach $$$j$$$ while using at least one $$$(k + i)$$$ step, but no larger steps. Then $$$dp[i][j] = dp[i][j - (k + i)] + dp[i - 1][j - (k + i)]$$$.

To save space, I only maintained two rows, since each row only depends on the previous row. To save time, I also kept track of what the first non-zero element of each column will be, so I don't iterate over the elements on the left (which I know are 0).

Use dp.

It is easy to see the steps must be not big,about $$$\sqrt{n}$$$.

Set $$$f_{i,j}$$$ as the answer of $$$i$$$ steps reach $$$j$$$.

$$$f_{i,j}=\sum_{l=1}^{j-1} f_l*[(j-l) \mod (k+i-1) == 0]$$$

Then we can use rolling arrays to optimize the memory and use prefix sum to optimize the time.

Then it is a $$$O(n\sqrt{n})$$$ solution.

Code: 166958668

Same, except that I slept instead of playing Osu

With respect, will you please explain what does 'speedforces' mean? I see this term a lot. But I don't know what it means.

I solved it using dp. DPij means the number of sets such that the last number is i and the last permormed operation was with k' = k + j. Then ans[i] is the sum of DPij over all j. But if you do this naively the solution will run in O(n^2). Think how to optimize this dp to run in O(n * sqrt(n)).

That's what I was thinkiiinng! Great to finally find some support <3

Zig-zag too consists of some other paths like when you choose to complete all columns of a row first!

It can be zigzag, then a big turn.

You can do a little bit of zigzag at the beginning and then clockwise or counterclockwise

There's more than 3. You have a prefix of zigzag moves, and then remaining clockwise or counterclockwise. The choice is where you stop zigzagging.

you should check all possible ways like that:

start and go clockwise
X---|
<--|

down and counterclockwise
X<--|
X --|

again up and clockwise
XX -|
XX<-|

and so on

I also thought that. But the number of solves is to little for it to be that easy.

During the zigzag, you can start a clockwise or counterclockwise path at any point.

To be completely honest, I don't possibly see how they would think this is a Div2C. In my opinion, it would at least be a Div2D, or even a E for an educational round.

Great fortune indeed

great_fortune

The moments why we cpers like cp....

Hello Potato Sir. You already left Cp . I hope one day you will see this and reply me.

Not true, your path consists of a prefix of zigzags, followed by a suffix of the 2 straight lines. So there are more than 3 possible paths.

The robot can zigzag for a few columns and then go clockwise/anticlockwise.

Take a look at Ticket 15984 from CF Stress for a counter example.

Anytime you decide to pick the neighbour on the right, you'll have to traverse the grid either clockwise or counter-clockwise in order to visit all indexes in the grid. Seems like more of a DP problem.

1. Zig-Zag till a certain index
2. Clockwise / Counter-Clockwise

It should pass, but with proper realisation

It has to pass, but yes, the limits are very strict.

Also, it seems, that the whole array is bigger, than memory limit. I instead used only two rows.

probably because of the log factor of the std::map.