NRWP - Editorial

I also tried to use dp in bfs layers but a lot of problems arise. I don’t know how you managed to make it passed but I couldn’t.

First , seeing your code, you are just runing a bfs from the first root the you find. But then, the maximum size of the queue can be 2 \times \sqrt N. So K can be roughly 27 in worst case.

Imagine something like this:

expand

The number 1 is your root for BFS. The second layer will have 1 node , the third layer will have 3 nodes, then 5 and so on. If the maximum number of nodes is 200, then your last layer will have 27 nodes.

Try this input : https://ideone.com/95BxyF

It will make you to use 2^27 * 197 of memory and your code will fail.

I managed to “solve” this situation doing this : Simulate the BFS with every node as a root and pick the one that minimize the maximum size of the BFS queue. I think it can be proof that with this approach the maximum size is at most 19 (or maybe 15), because I think K can be also bigger than the maximum size of the bfs queue.

But even with that I couldn’t make it passed the testcases.

By the way, hats off to you , @carre . Amazing problem and editorial

1 Like

I had a similar solution to korneev. BFS may not always find it, but I’d conjecture there always exists a variable ordering for which you need to keep a history of at most 14. You can find that variable ordering by finding an appropriate vector in R^2, taking the dot product of each variable’s position with that vector, and sorting by the dot product.

My argument isn’t entirely rigorous, but here goes:

Suppose there’s no such vector. Then, for every direction, we can find a line in the plane separating our variables into a “left” half on one side of the line and and “right” half on the other such that 15 or more “left” vertices are adjacent to at least one “right” vertex.

There ought to be an isodiametric inequality of sorts showing that the smallest figure in the lattice with this property is a 15x15 square, which has 225 cells.

Indeed, I had the similar concerns and a way to solve them in my mind.
Though, my initial solution had passed all the tests and I didn’t implement it.

how can I generate such a big testcase?

writing a little code that do it for you. Something like this will generate random values for your h’s:

for (int i=0;i<H;++i){
    for(int j=0;j<W;++j)
        cout << rand()%1000 << " ";
    cout << '\n';
}

Anyway, if you accept a little advice, in case you are learning how to generate 1E6 inputs may be you should focus in other kind of problems, this one won’t help you with basic steps of coding.

1 Like

thank you so much
but my code giving correct ans for this testcase as well

please, check if you are not changing W and H meaning. I think the error can be due to that…

if (y+1<h){p1=B1[x][y+1].f;}else {p1=0;}

there you compare the second item of B1 with h, but h should be the limit of the first item, according to this line:

B1[B[i][0]][B[i][1]]

If that’s not the case, in a couple of hours I can check it more seriusly

Hey, if you are interesting to learn about stress testing I do have generator / reference solution for this problem.
To try this out you need to:

  1. Clone my repository git clone https://github.com/AndreyKorneev/competivie-programming.git
  2. Go to the repository root cd competivie-programming (Yep, sorry for the typo in repository name)
  3. Restore the problem from examples ./run.sh restore examples/codechef/MAY20/NRWP
  4. Replace main.cpp in the repository root with your code.
  5. Do stress testing ./run.sh stress

Things might not work as expected since I’m the only user of my setup.
Feel free to ping me in PM on GitHub or codeforces (james007) if you face any trouble.

ok, I checked it. Here is your code with some modifications:

https://www.codechef.com/viewsolution/33069641

  • as I mentioned before, there’s a swap between w and h when you check x+1 and y+1.
  • out of bounds in the initialization of B
  • you initialize B1.s to 0 but then 0 is a valid particle, you should initialize to a number that can’t be a particle (I used 204)

In case you are interested, the following code implements the brute force approach in a simple way, what often makes the code easier to debug:

https://www.codechef.com/viewsolution/33069712

thank you
and sorry this is very silly mistake

Can anyone illustrate this solution graphically, still finding it difficult to understand this editorial.

Are you familiar with max flow algorithms and max-flow min-cut theorem?

@carre I just read about it. But I still need descriptive comments in the tester’s solution. It’s really daunting to understand code despite running it line by line using debugger. Comments would be helpful. I read max-flow algorith for the first time.

OK. If you accept advice, if you are starting with max flow, you should practice it first, it is an important topic and not so easy. You can start with simple problems of direct implementation of the most widely used maximum flow algorithms: Ford-Fulkerson, Edmonds-Karp and Dinic. You can then move on to the minimum-cut max-flow theorem. Those steps are prerequisites for the solution explained in the editorial.

I don’t think the comments on the tester solution would be any more helpful. That solution is conceptually identical to my solution (setter solution) which is full of comments except for the dinic’s algorithm lines. The details of dinic’s algorithms are out of range of the editorial.

2 Likes

Thanks for the advice. I saw the setter’s solution can you tell me what is the function mf,bfs,dfs for ?

As you can see, they are inside the namespace called “dinic”, they are functions of the dinic’s algorithm employed to find the max flow of the network.

There are several resources to read about dinic’s algorithm and one of them is this. As said before, the explanations of the details of dinic’s algorithm is beyond the scope of this editorial.

okay thanks

Can someone explain me:
What is meaning of “rev” in setters code?
What is this (int)g[t].size() in

edge a{t, (int)g[t].size(), 0, cap};
edge b{s, (int)g[s].size(), 0, cap};

How is it useful in dfs part?
image
Thanks in advance

g[i] is a vector that contains the edges coming out from node i. Supose you have and edge from i to j, let’s call it edge e_{ij}, then you also have a reversed edge from j to i, called e_{ji}, that reversed edge is an element of the vector g[j]. The rev property of edge e_{ij} is the index of the vector g[j] where the back edge e_{ji} is located. That information let you access to the reversed edge from the directed edge.

When you send flow df throw the e_{ij} edge you need to update the flow of the reversed edge by -df and that’s when you use the rev property.

Thanks a lot . I got it. :slight_smile: