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

Unrated rounds are already technically in codeforces (virtual rounds).

Oh I will downvote your comment buddy.

all the best

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

You made it congrats.

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!

good luck

well next time then

It really is.

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

Where is this photo from?

Div 2 ABFDE + Div 1 C actually

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)

It's called the exponential round, every two problems you loose one order of magnitude of the contestants :).

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.

Hint:Use prefix sum to speed the dp up!

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.

zigzag + clock or counter?

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.

I also thought this way and wrote kinda naive approach and with lot of lines of code..

Your text to link here...

Maybe Zigzag till some index and later either cw or acw. I couldn't implement it tho :(

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.