find the shortest path upto k/2 moves and then come back along the same path...

When k is even, we need to find the shortest path from starting position by performing only k/2 steps. And then traverse back along this path to get the required answer for k steps.

The shortest path is not with length k, but with length i. If k/i is even, we can go this path from start to end and then from end to start all the time. So finally we can return u.

Hey, your comparator isn't defining the equality condition, when will two pairs be equal? Try changing line 157 from "return 1;" to "return 0;", it will work :)

You are returning 1 for this case:

         if (a.row == b.row) {
          return 1;
         }

Ideally it should return 0. What seems to be happening is, when a=b and b=c then a=c but due to above case, a=c is probably not holding true

You can think about it like this. Consider the sum of the 2 coordinates. Every step you take changes the parity of this sum. To return to your starting point, your parity can only change an even number of times, but it changes exactly k times. Therefore, k must be even.

All the nodes a[i][j] will be connected only to the nodes a[k][l] if i+j and k+l has opposite parity.

So the given graph can be divided into two parts, one with the parity of sum of indices as even and other as odd.

Hence the given graph is bipartite.

Graph is always bipartite when it has no odd simple cycles. Let's take any cycle in this graph. Let's add some vertices to it which still form a cycle with the past ones. Their count will be 3..5..7 and so on. Besides, we must remove one edge, because it's needed to make the cycle simple.

Picture (sorry for Paint):

Because any n * m grid can be converted to a chess board.

Can we solve D using Dijkstra? I was getting wrong ans, not sure if I'm missing anything... https://mirror.codeforces.com/contest/1517/submission/114047555

Sorry for replying to such an old comment. Found a testcase which might help anyone facing the same problem in future.

3 2 8
9
100
3
9 5
5 2

But how is this always minimum? What if we go out through a particular edge but return through a different edge?

You iterate over length of $$$CC...C$$$ and the minimum acceptable length of $$$PP...P$$$ can be found using binary search or two pointers, because all the numbers in the array are positive, and function $$$\sum_P - \sum_C$$$ is monotonous.

If you have some kind of alternating prefix sum array to quickly calculate the sum of P if some range is PCPCPC(let's call it $$$pr$$$ and if the range is between the $$$i+1$$$-th and the $$$j$$$-th element then the sum is $$$pr_j-pr_i$$$), when fixing the point where you switch from PCPCPC to PPPPPP(let's call it $$$j$$$), if the point where you switch from CCCCCC to PCPCPC is $$$i$$$, then the condition is $$$pr_j-pr_i+sum(j+1..n) \geq \left \lfloor{\frac{sum(array)}{2}+1}\right \rfloor$$$. You can find the maximum $$$i$$$ for which that condition holds using either binary search or 2 pointers.

My solution is similar to dorijanlendvaj's for the part with alternate partial sum, but I used a data structure (e.g. fenwick tree, segment tree, treap) to maintain the number of i satisfying the inequality. For stupid people like me who can't spot the obvious property of monotonicity, it is a lot more intuitive. The code can also be pretty short if you are familiar with data structures, check my code here: 114032392.

My approach is also similar to editorial.

Consider a rubber attached to the point i,i. We want to stretch the rubber p[i] times. So the optimal choice is to stretch the rubber in the following order

1-Strecth the rubber up

2-Strecth the rubber left

3-Strecth the rubber down

4-Strecth the rubber right

This ordering will always ensure that we don't have any empty space left. See submission for more details:114016611

Video Editorial for problem B: https://www.youtube.com/watch?v=F5zq_BU25Ac&t=397s

I think I've seen it before, it's to evade the plagiarism checker. Maybe you could report that to MikeMirzayanov.

The problem has two types of forbidden pattern: the "square" and the "parallelogram". the square corresponds to 1-0-3-2-1 while parallelogram to 1-0-2-3-1. On the surface, it seems you have to add two kind of edges between rows: 0-3 1-2 (vertical ones) and 0->2 1->3 (diagonal ones)

But the key observation is that you don't need to, you only need to add edges 0-3 and 1-2. The reason is because to check for parallelogram, you can actually just use the same check: whether a path 0-1-2-3 exists. If such a path exist, then it must either be a square or a parallelogram, e.g.:

...10...01...
...23...32...

for squares and

...10...01...
..32.....23..

for parallelograms

Therefore, we consider the acyclic graph where all "0" nodes have edge to "1" node, all "1" node to "2" nodes, and all "2" nodes to "3" nodes. in this acyclic graph, we want to cut fewest weight nodes so that no path exists from "0" to "3". This can now be done easily using min cut.

It is not possible.

Supposition: The optimal cost to travel k/2 steps is C.

If you move k/2 steps with cost C and if there exist a returning path with length k/2 that has C' < C.Then you can move in the later path to get a cost of C'.But this is not possible because of the supposition.

Hence we can always travel k/2 steps and return with the same path.

For Dijkstra's, the exit condition should be -

if (dist[u.r][u.c][u.lv] < u.w)
        continue;

instead of

if(dist[u.r][u.c][u.lv] != u.w)
        continue;

check out my submission, I just modified this line and it passses — https://mirror.codeforces.com/contest/1517/submission/114073092

By the way, can you explain your logic for Multi-Source Dijkstra's? Mostly why this holds true in this problem?

Also, the queue solution should be incorrect, because Dijkstra's requires a priority queue for the same?

I haven't yet tried, but I guess you can optimize the dp with some heavy-light decomposition trick. I guess, since the number of dp states at node v is of O(depth_of_subree_rooted_at_v), when dealing with node v, you can inherit dp states from the heavy child (child with the maximum subtree depth) and iterate the rest children. That way, you end up with a O(nlogn) dp per radius, then O(n^2 log n) for all radius.

Please use pastebin or use spoiler to share your code, directly pasting the code pollutes the blog :)

Well, you can prove to yourself that the last digit of "n" is always (n%10) = n modulo 10 (the rest when you devide n by 10. Now, you use a while and at every step you add n%10(last digit) and then devide n by 10 (that eliminates the last digit). You have to do this until n is equal to 0. When that happens you stop the iterration and that's the sum. Hope it was not a joke and I actually helped. :))

C and P are two sets of all indexes of "a" (together — "n" elements). Indexes of C is growing wider left-to-right, and P — right-to-left. If for some ci-c(i-1) > 2 than there should be two P's in a row between them. And this means there can't be no more P's to the left from them, and to the right(max — 1), because pi-p(i-1) become 1, and to jump over C it need to become 2 — this breaks monotonic rule. And so on.

Check this image out —

Basically, get the top m minimum numbers from the all the entries, and position them stategically such that the order of min elements is followed.

As you can see the image, we want to permute each row, such that the min numbers(in red) are positioned one after the other.

You can check my submission for more details — https://mirror.codeforces.com/contest/1517/submission/114011935

The same thing happened to me. You are taking the input wrong way.

We want to know more of your liking.