All rounds are created equally.

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

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://codeforces.me/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 \lt 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 \lt 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

Try this case

3
1 2
1 2
2 12

lol was about to comment that

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}