Isn't it O(T*2^LEN)?

EDIT: No, there is popcount in every recursion

Correct

I was mistaken I didn't see the contraints

What's the formula to calculate it?

Changing the total number of cases can also change B score. For example:

b = 50, 100, 100, 100 -> score = 300

b = 50, 100, 100, 100, 0 -> score = 350

I can't make any sense of the code used to calculate pos[i][j] in problem E

Ah right, I didn't see that part: "The sum of n over all test cases will not exceed 1000". Thanks.

I still think the solution in the editorial is better and is O(n), the one in C++ for example, but maybe I'm missing something

UPD: actually with that constraint on n I guess it actually doesn't matter

I'm sorry I didn't do CP in a while. Wouldn't your solution be O(t*n*n) which is O(10^9)? With the solution on the editorial you can get O(t*18000)

Yes this is a lot faster than without dp, can you explain briefly the dp algorithm done in linear time?

EDIT: Nvm I think I got it, it is really simple indeed

This is exactly what I did, but I realized it after I coded that mess.

Mine passaed 45632893 (After the contest and the code is probably bad)

The number of paths for corner to corner can be seen as a permutation with repetition with formula (m + n)!/(m!*n!).

The number of paths from a corner to the diagonal is 2^20 at most. When n = m = 20 each path is 20 steps and each step either down or right.

40264790 like this

Is the title and the description of div2 D incorrect? I still didn't understand the problem.

Pave: cover (a piece of ground) with concrete, asphalt, stones, or bricks; lay paving over.

What does it mean to pave a parallelepiped?

Exactly like last div2 round...

I'm not gonna say this contest is bad because I'm always grateful when there is a new contest, but the problems' difficulty distribution makes no sense: A, B, and C were all the same difficulty (actually A is probably the hardest). It doesn't even test programming skill, just write fast and pray there aren't any bugs and you get +100 rating.

Did anyone actually solve problem B with a solution different from "01010101..."? That would be hilarious.

Oh yea I just got confused ty

In the graph of problem E how do I calculate the maximum number of edges?

Nice problems, thank you!

Could he use it in an non-educational round?

I'm kinda bad at explaining recursion..

In my solution I recur from 9 to 0 and iterate (from 1 to the number of times that digit appears) = j. To calculate the number of ways to add the digit do the current string with length = m, I do (j + m)! / (j! * m!). Then I continue recursion passing this result.

I divide by j! because the digit is repeated j times and I divide by m! because I can't change the order of the current string.

The recursive solution for E is nicer and simpler.

What is D complexity? I think O(2*m + n)

This is the code if you couldn't find it 39498091.

-I decide the next bucket by lower_bound(a[i] % m) in a set of buckets, every time a bucket is full I erase it

-I add to a[i] the difference between the buckets, which is how many times I have to increase it

-The final array is the original one that I changed every time

Consider every reminder c[i] a container that can hold at max n/m numbers. As you read the input you put a[i] in the container c[ a[i] % m ], if it's full: you put it in the next available container and add to a[i] the number of steps. To do it quickly the next available container is registered in another array.

Let me know if that makes sense.

EDIT: An array to store the next available container isn't good enough, a set is needed.

Same, I had problems with B corner cases and I didn't bother reading C because there was little time left. After the end of the contest I coded C in literally 5 minutes.

That solution would give TLE because it iterates all the numbers until 1e9

Because you put k = 7 elements in the array b allocated for n = 3 elements.

Yes I know, I couldn't figure the equation. Where did you get it? Because I would have used something with Pythagoras. I don't understand why it works in your way.

First I checked every vertex and the center point of the oblique square, if it is contained in the other square then the answer is YES.

Then I rotated the coordinates axes of 45 degrees ( https://en.wikipedia.org/wiki/Rotation_of_axes ) and did the opposite.

It probably isn't the best way

EDIT: Fuck yes it got accepted

MRW I mistyped one variable in both A and B and the pretests didn't catch it.

Very cool. Interesting problem, but really hit or miss I think.

C fucked me up, was there an easy way I missed? Can anyone explain the solution?

You are writing in an empty string (st) without changing its size, so it's undefined behavior. When stuff like this happens it's usually because you allocated the memory badly.

Probably not because the constraint on the input is a[i] <= 1e6 so there aren't many numbers to create collisions.

1

)(

All problems were doable and I liked them, but I think there is too little difference in difficulty form C to F

What?

How could I have known, so basically I can't use unordered_set in a contest? Or I should write my hash function I guess lol.

Test 27 of problem D is made to fail if unordered_set is used, why is that a thing?

EDIT: It fails with C++14 and passes with C++17, fuck me I guess.

Also use unordered_map so the find complexity is O(1) instead of O(logn)

I read "connected components with equal size" instead of "even size" in C. Yikes

For G you don't need to iterate all the exams every day.

38195700 complexity is O(n*logm) insted of O(n*m)

I didn't read the queries were in increasing order :D

No because the first time 1 person gets out.

There can be [1, 9] people on the bus before the first stop; if there were 10, after the second stop there are 11, and there has to be at least one before first stop.

Can someone look at these 2 solutions of C: 38161183 38162269.

The first has complexity O(k*k) the second O(k*logk) and yet the second takes 1.5 s more?? What am I missing?

Check my solution, it gets low execution time and it's different than anyone else's I've seen.38076021

I had the same issue: 38055867 I couldn't figure it out.

If the matrix is perfectly symmetric you don't need to count the number of paths to know they are they same number. They are literally the same paths, no need for more proof.