All rounds are created equally.

i want to know the end of the story how many problem did you solve ?

Yes, only after the announcement for the problem C :(

and i'll be there to discuss it with you aryanc403

i've been watching your past streams too .

Thanks

get job

Thanks for that , would love to participate in that ......hoping for a positive delta this time...

same

Yes, it is.

Different scoring type and usually educational rounds are supposed to be "education" so you might encounter more standards.

I couldn't able to come up with an solution for this problem tried using bit manipulation but got wa on testcase 3 do we have to solve this using any other approach.

This is uncomfortably true...

Using Flows

I guess, Flows with Demands should satisfy the problem. Just throwing in some virtual nodes for outflow from each node and inflow to each node should do the job. Here, a node is a row/column, and edges are delta-based flows on flipping cells. Note that we know the original sum across rows/columns, and only care about needed deltas through flipping. This delta determines the demands on inflow/outflow virtual nodes.

Pretty much the same problem

Usually the actual rating change is higher than what is shown in by carrot extension, especially in edu rounds. Unless you get FST

Make a flow network with n+m+2 edges. One is sink, one is source and n vertices for rows and m for columns. Make edges with capacity r[i] to all rows from source and edges of capacity c[j] and cost 0 from columns to sink. Also make edges from row i to column j with capacity 1 and cost 1-a[i][j]. Your answer is minimum cost max flow plus the number of a[i][j] == 1 where the i -> j edge was not taken.

i tried to solve using multiset itself but got tle for 8th testcase, tried using two vector after the contest got summited

https://mirror.codeforces.com/contest/1913/submission/237823558

This test fails

4 4
0 0 0 1 
0 1 1 0 
0 1 1 0 
1 1 0 0 
1 3 1 2 
2 0 2 3 

Also this

3 3
0 0 0 
1 0 1 
1 0 0 
1 1 2 
1 3 0 

And this

2 2
1 1 
0 1 
1 2 
1 2 

I tried the formula dp[i] = Sigma(dp[j-1]) with a[j] >= a[i] and j <= i result is the product dp of 2 sequences a[0] ... . a[minimum_index] and a[n-1] ... a[minimum_index] but wrong, do you have any other solution

Unfortunately it was easy :(

A to C is trash btw, but D made the contest worth giving I think (even though I still cannot get it)

DP on suffixes, maintained with a monotonic stack.

Compute for each index how many arrays you can reach that start with it, ignoring elements before it. You can delete any prefix starting from it that contains no smaller values (the monotonic stack is for this) or delete a prefix immediately after it to reach smaller elements further away. I handled this part with a set but upon further inspection it’s really just a copy of my stack ;)

The problem is quite similar to Indonesian NOI contest here

I think the approach should be quite similar. Assume $$$dp_i$$$ is the number of ways that the array ends with $$$p_i$$$, then we can consider that for a range $$$(l, r)$$$ we can calculate number of ways when $$$p_l$$$ or $$$p_r$$$ is the minimum

For each $$$r$$$, there are two possibilities :

• find conditions for all values $$$l < r$$$ where $$$p_l$$$ is the minimum from $$$(l, r)$$$ then $$$dp_l$$$ is a contributing factor to $$$dp_r$$$

• find conditions for all values $$$l < r$$$ where $$$p_r$$$ is the minimum from $$$(l, r)$$$. To do this, find an index $$$i$$$ such that $$$i$$$ is the previous smaller element of $$$r$$$. Then $$$dp_{i+1}, dp_{i+2}, ..., dp_{r-1}$$$ are contributing factor of $$$dp_r$$$

For the first case, we can maintain a monotonic stack and maintain the sum of all dp within the stack

For the second case, we can use a monotonic stack to maintain previous smaller elements for each index and to find the sum of the dp we can use a prefix sum of dp

you can do it with DnC on the minimums of the array, split the array on the minima and calculate recursively for the left and the right part and merge those results

The hardest step of problem D is to come up with a correct DP. Optimizing it from $$$\mathcal O(n^2)$$$ to $$$\mathcal O(n)$$$ is easy.

Luckily no one submitted this problem during the contest :(

bro you didnt even solved it XD

mincost maxflow on a bipartite graph

With flow min cost, I didn't manage to create a net during the contest sadly ;d

make both 1e5 / 2

what do you do in the add?

Try this case

3
1 2
1 2
2 12

lol was about to comment that

hoping for +ve delta!!!

Well the proof is not obvious. It only works for set of numbers where all smaller numbers divide each element in the set, for example here it is powers of two. It wouldnt work in cases like {1,3,5}

speedforces

I'm getting +ve delta so :noo:

It doesn't effect larger group of people so it should not be unrated

It has been said before. Problems will repeat, but the round will not be unrated if not done intentionally.

lol cry about it

Could you share ur intuition for C? C got a lot of ACs . Everybody figured it out so quickly except me

Seems unhackable. C++ compiler optimization too OP

The complier understand what you are doing with

while (sum >= p && stock[i]) sum -= p, stock[i]--;

And convert it to a O(1) operation.

currently trying near $$$48000$$$ add queries, and I don't quite know why it isn't getting hacked (or why the setters even set limits too loose)

This is because of the y = 0 case when you use __lg: https://mirror.codeforces.com/contest/1913/submission/237832586 This is because the implementation of __lg may be different on the different compilers. Functions starting with __ are not necessarily consistent across compilers.

2^n is greater than the summation of 1+2+4+8+...2^n-1 so you can be greedy about using your smaller powers because they can never contribute to be a bigger one

binary representation of a number?

Yes, you always get a new rating for all contests that are rated for you. This contest is rated for anyone under 2100. Considering that you're currently unrated (that's 0 basically), it IS rated for you.

Rating works as follows — for any rated contest that you give, your rating is updated based on your performance. If you perform well, it increases, else, it decreases. Anyway, rating is just one factor to competing, in the long run, the experience results in a net positive anyhow. Have fun! :)

What's the worse time complexity of your approach? Isn't it O(m^2)?