http://mirror.codeforces.com/blog/entry/61285 Pls see this...getting some issue in contest 504 Question D

From what I see and understand, even contest 505 will be combiner round right?

Да

https://www.youtube.com/watch?v=0vtLXNFdxJY

Hope so!

+1

Are You Contributed?

You can if you want. :)

There will be both languages

We hope so ! Good Luck !

How to solve D?

Numbers of ACs to E is basically one third of ACs to D. I wouldn't call that big jump in difficulty.

I don't think E was very hard for a div1C difficulty problem.

It even had 2 times higher query limit than it needed.

Compilers used in local machines and Codeforces servers might not be the same. So, next time, perhaps you should consider testing something through "Custom invocation" first.

In C++ programming mistakes won't necessarily behave like you expect them to. Entering undefined behavior means anything can happen, the program may crash, print an incorrect answer or even appear to "work".

Which one failed? The hack, or the generator/validator/checker?

If it was the hack, show the submission you intended to hack, so we can have a brief overview.

My solution for E also only need 2n - 2 query. The 4n query limit is probably to distract the contestant.

Yeah, my solution works in 2*n — 2 queries too

I used simple set for F and I would probably get TLE. I used 2*n-2 queries for E too.

In F, one can use path compression. 41719592

i didn't use hld but you can i guess, i changed updates to — minimize edges between a node x and an ancestor y of x with value val. I kept priority queue for each node, then added smaller queue to bigger one in dfs when traversing the tree. So i found the value of each edge offline.

I think I have a cute way to get rid of HLD!

We have some data of the type "All the edges in the path from u to v have to be at most x", and we want to find the upper bound for each edge. We can assume u is always an ancestor of v.

Build array bound[MAXN][LOG(MAXN)], which means the edges in the path from v and it's 2^b-th parent must be at least bound[v][b]. And also we define par[v][b] as 2^b-th parent of v. Then we can easily decompose paths to blocks that exist in bound array. And after all, we do the following:

for(int b = B - 1; b >= 1; b--)
	for(int i = 0; i < n; i++)
	{
		int x = bound[i][b];
		bound[i][b - 1] = min(bound[i][b - 1], x);
		bound[par[i][b - 1]][b - 1] = min(x, bound[par[i][b - 1]][b - 1]);
	}

and bound[v][0] is the upper bound for the edge between v and it's parent.

A way to get rid of HLD is to use union-find set.

Consider this process: for each i, mark all edges in the path between fa_i and fb_i with value fw_i on MST, if an edge has been marked, then skip. Because each edge will be marked at most once, we can optimize the complexity of finding next edge which hasn't been marked.

Use a union-find set to maintain all nodes, at the beginning all sets contain only one node. If we mark an edge (p_i, i) (p_i is the father of i on MST), merge i's set into p_i's set. If we do this, at any time the representative element of i's set is a node j, while edge (p_j, j) is the first edge from i to the root which hasn't been marked.

While marking all edges in the path between fa_i and fb_i, let u = fa_i, v = fb_i. Each step, let u, v be the representative element of its set, select the deeper node, find the first edge e using union-find set, and marked e with value fw_i, until u = v.

I'm not sure because I didn't fail on that test but might it just be an empty grid? (of any size, probably >2) There's an edge case where if you don't change your preferred move on the second half then the paths might not line up.

Yeah, Yeah, Yeah downvotes are proof for F***forces

The last query was with i = q, so q has to appear at least in one position.

There has to be at least one 5. 5 cannot be overwritten

because last query will affect atleast 1 value. there would be atleast one 5 in the final answer.

every query has to be applied on atleast one element of the array. So if the output is 1 1 1 that means you didnt apply 2 3 4 5 queries

because q = 5 should be in the final array

Write Blogewoosh #3 about it

Or maybe Dilworth things?

I replace your dinic algorithm with HLPP. It's more than 100 times faster now.

And it can finish in about 8 seconds on my own laptop. You dinic code is still running now. However, it can't finish in 10 seconds on the custom test.

Maybe we can squeeze it into the time limit by a faster flow algorithm/implementation or reducing the number of edges.

This sounds ridiculous. What this problem has done to you so that it activated so much hatred in you? It was cute and simple.