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.

Then why did you create interactive problem, if you hate them.
https://www.codechef.com/AUG18A/problems/INMAT

Subsequence is a string that can be obtained after deleting some symbols from original string

No, 592A - PawnChess seems to be harder :)

You can check 200A - Cinema.

No , it was rather easy but some noobs made stupid mistakes

Might be because of including 0's in range minimum.

Try this: 8 4 0 1 0 2 4 0 2 3

possible answer: YES 1 1 1 2 4 4 2 3

I had problems with test 7 too, but this test helped me.

3 3

0 1 3

YES

1 1 3 or 2 1 3

For each '(' find corresponding ')'. Delete these pairs from the string while its length is greater than k

your question is soo tough please wait Editorial like me!

t[:-len(v)].startswith(u) and t[len(u):].endswith(v)

After a red bold number showed, I found this — t[:-0].

Maybe Python will help.

I tried Python's unfamiliar regular expression, found it didn't work, then waste a lot of time using C++'s strtok...

All I actually need is Python's split、startswith、endswith...

I have a solution using STL string functions xD

But you didn't lock any problems...

really ez, just don't take the case s.size() > t.size() and s dosen't have the character *, but take the case s.size() — 1 > t.size() ans s does have the character *, REALLY EASY

if there are three indices i < j < k such that a_i = a_k and a_i > a_j and a_j > 0 then the answer is NO, it can be checked with segment tree. if there is no q in array and no 0 in array, then the answer is NO. otherwise the answer is YES. if there is no q in array and there is any zero in array, make it equal to q. for each zero , make it equal to any neighbour nonzero element.

First, there are a few nasty cases related to the last query: is there any q in the input array, or else is there at least one zero to put it there...

After that, I had another approach, somewhat technical yet trivial on the other hand. For each query from 1 to q, remember the first and the last index for this query. (For query 1, let's say it covers the whole segment, just to get rid of zeroes.) Now process all queries in order; to do it in , we can just use a segment tree. Alternatively, a scanline-like approach would also work, treating first and last indices as "query started" and "query ended" events, and processing them from left to right. Finally, check that what we got corresponds to the non-zero entries of the given array.

Consider the construction of a as follows: First, place 1's from the start to the end. Then, place the smallest possible segments for each number (so, for query q, go from the first instance of q to the last one). If there are no instances of q, place it where you will eventually place the last query (so, don't worry about it). If the last query is empty according to above setup, put it on a 1. If the last query is empty and there are no 1's, then the situation is impossible.

Of course, this is O(NQ). We want to do it a bit faster, so let's store the ends of each segment in some array. Then, go from the first position of a to the end, while maintaining a priority queue of the segments you are currently looking at. For each number in a, add it to the queue. Check if that number is the end of a segment, if so, remove it from the queue. If at any point the highest number in the segments is greater than the number in a, then it is impossible. When you come to a zero, just put whatever number is in the queue currently or 1 if there are none. But, if it is the last zero and there is no segment with the last queue value, then place the last queue number instead.

I did D with just a priority queue by constructing what the array has to look like after the queries (41700329).

You find the leftmost appearance for every number, and the rightmost appearance for every number. Then, with a priority_queue, you go left to right, doing the following:

1. If the value at the current index is 0, continue
2. Otherwise, if it is the current indexes values leftmost appearance, add it into the priority queue
3. While the rightmost appearance of the topmost element of the priority queue is less than the current index, pop it.
4. If the priority queue is not empty, set the value at the current index in your construction to the largest value in the priority queue.

This achieves the same as having query i fill between leftmost appearance of i to rightmost appearance of i.

After this, if the number q (from the last query) doesn't appear, put it at some zero. If q doesn't appear, and no zeroes exist, fail. This is since all intervals have nonzero length.

Then check that at all indexes that don't contain zeroes in the original array, your construction matches the original array. If it doesn't, fail.

Then fill all zeroes with arbitrary adjacent elements, and output the construction.

Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Maybe this?

Don't be angry, be careful.

"Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream." EDIT: I got ninja'd.