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.

https://codeforces.net/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

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}

speedforces

I'm getting +ve delta so :noo:

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

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://codeforces.net/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)?

good one !

can you explain your approach how the index of element is helping you to construct the ans

as you stored (element,index) in root , what is the contribution of left ans and right ans

correct me if Iam wrong

even I thought of the contribution of minimum index but couldn't proceed:D

Nice One!

Scroll up

you need to be true sigma ioi enjoyer to understand this code

carrot extension

The hacked case is not considered in the original test cases yet

bruh...you literally submitted it in practice

Rating changes for educational rounds usually take more time.

They forgot about them