We need to determine choice for each city. Then sum it for each candidate and determine the winner.

*O*(*n* * *m*)

Lets find which variant is interesting. For Andrew is no need a variant wherein |*a* - *m*| > 1 because we can increase probability of victory if we will be closer to m. Then we consider two variants, *a* = *c* - 1 and *a* = *c* + 1. Probability of victory will be *c* / *n* for first variant and (*n* - *c* + 1) / *n* for second.

We need to choose better variant, also we must keep in mind case of *n* = 1.

*O*(1)

Lets find how replacements occur. If we have segment of points with length *l*,we need *l* - 1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.

Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.

*O*(*n* + *m*)

We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.

We can make a palindrome if quantity of uneven entries of each letter is less than 2.

This function can be counted for each prefix in bypass for each depth.

For saving the memory bit compression can be used considering that we need only parity and function is xor.

*O*(*m* * (*log* + 26) + *n*)

D had a offline solution too in *O*(*n* + *m* * (26 / 32)) time and *O*(*n* * 26 / 8) memory

We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.

From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.

For saving memory we need to store two latest layers.

*O*(*n*^{3}) — time and *O*(*n*^{2}) — memory

Auto comment: topic has been translated by josdas(original revision, translated revision, compare)thanks for Editorial :)))

Can you explain Problem D in a bit more detail.What is meant by in and out time of vertex.What is bypass the prefix.Doesn't makes much sense to average people like me.

Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is:

Depth 1: 1

Depth 2: 2, 3, 4

Depth 3: 5, 6

This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows:

DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1

This can be addressed by applying the following pseudo-code:

time = 1;

DFS(vertex u)

in[u] = time ++;

for each son v

DFS(v)

out[u] = time++;

The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by <v, h>, we find the answer as follows.

Case 1:if h is no more than the depth of v, return "Yes".Case 2:if v has no posterity that locates in depth h, then return "Yes".Case 3:Otherwise, find the required vertices in depth h, and judge "Yes" or "No".It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code:

l = 0, r = Depth[h].size() -1, ans_left = -1;

while( l <= r )

m = (l + r) >> 1;

if vertex Depth[h][m] is posterity of v

ans_left = m, r = m -1;

else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v

l = m + 1;

else

r = m -1;

Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list.

An accepted source code: 12519227

I read your code. I didn't get one thing. In the part-> int x = mp[make_pair(v, h)]; if( x == 1 ) puts("Yes"); else if( x == -1 ) puts("No"); else run(v, h); }

Why do you even check for the value of x? Why don't you straight away use run(v, h) everytime? What is the use of even using a map? It will only be helpful if the same inputs are encountered. Right?

It is a memorization technique.

how does that check if the letters form a palindrome? I understand why you must use dfs to find the depth of nodes but I don't see how recording the in and out times of a node in the algorithm helps you solve this problem. Can you explain a bit?

Ok I solved it. Pretty easy to be honest, it's hard only at first.

Can you explain me your time complexity? It seems to me that for each of the m query, you do two binary searches, and count the characters between ans1 and ans2. However, if (ans2-ans1) is big, isn't it going to be slow?

I see you used map there. But how does it guarantee fast time complexity? I hope my question makes sense.

How do we check whether the letters form a palindrome? Iterating through all the elements in the range might get a TLE exception.

Please elaborate Problem E also.You have not explained very clearly?

Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).

Now, the basic recurrence without memoization can be seen as :

Also,

one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.

I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(

thanks a lot :) this is so much clearer (y)

Could you explain more about how your dp solutions uses O(N^2) memory instead of O(n^3)? I am struggling to understand it.

can u tell me more clear how to find y2?

Assuming 1 based indexing and the corners to be at (1,1) and (n, m).

Now, if we are at (x1, y1), it means that the count of total moves is :

moves = (x1 — 1) + (y1 — 1) [Because at each step either x1 increments by one or y1 increments by one]

Similarly, from bottom corner we get

moves = (n — x2) + (m — y2)

So y2 = n + m — x2 — x1 — y1 + 2

thanks, now understand.

Can you explain the memory optimization part a bit more?? and give the code please?? Would be really helpful

The problems were great, but these explanations are a bit lacking. Could you please explain the solutions in more detail?

Second problem was top!! Just shows how important boundary conditions are while testing. Lesson learnt.

C can be solved in _ O(nlogn+mlogn) _ using a Segment Tree, storing for each node the number of operation needed to transform the whole segment, and another 2 variables pref,and suff which allows to know if the segment has a "dot"-1prefix or "dot-1suffix" :) is a simple solution but it needs more memory 12518296

I solved it with the same complexity but using binary indexed tree

But this overkilles the problem alot in my opinion

This solution is the sane as before but without logn

For C — regarding "...Quantity of segments can be supported by array." — we actually don't need to keep the segments. Rather we keep only current value of f() — and when we put a new symbol to the string — then f() changes by +-2, +-1 or 0. This depends solely on the old symbol and 2 its neighbors.

12510601

I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578

In the edge cases

`else if (t == n - 1)`

and`else if (t == 0)`

the`cur`

variable is not updated.Also I believe there can be out of bound issues in those edge cases, when n is 1 — as

`s[t - 1]`

and`s[1]`

indexes are accessed there, which is surely beyond the string limits.A hint: you can also avoid dealing with those edge cases if you add a letter to the beginning and to the end of the string. This operation doesn't change f(s). After that your string will be of length n + 2 and all the replacement operations on it will be between indexes 1 and n inclusive — so the neighbours will never be out of string bounds.

This makes code smaller — i.e. less errors possible, faster to type and verify.

This is a general idea in many tasks — instead of dealing with edge cases — extend the field of work and work inside a sub field of that.

Oh, that's nice, thank you. Surely will use this trick next time.

this idea can save a lot of time from a newbie's point of view,thankyou!! :)

At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.

Anyways, here is my solution if anybody needs more help: 12512037

Great, thanks, so simple :) AC 12522984

I am struggling with problem C

Can anyone give me a simplified explanation to it?

Thanks

Consider the simplest case: The string, of length

L, is formed by all dots. Clearlyf(s) =L- 1.Imagine there

kstrings of consecutive dots of lengthL_{1},L_{2}, ...L_{k}, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,Let's see how we can perform updates in constant time.

Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.

Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.

Case 3: A new segment is added (of length 1). This is the same as Case 2.

Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.

Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.

So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.

Thanks alot I solved it correctly ... But when i surfed the internet , i found an algorithm (data structure) called suffix array . Can it be used to solve this problem?

Have a look at this comment. Comment Here...

Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).Hi, I can't figure out what's wrong with my solution for D... Here it is: http://codeforces.com/contest/570/submission/12521712 Please help!

Problem D : Beware, Even printf , scanf giving TLE ;( using fast I/O got ACCEPTED .

Your solution

O(m*log* 26 +n). It is close to time limit.I know, My bad , this was the solution i cud get along.

My solution took 1996 ms. I'm running in the house yelling "Damn!".

Could someone please give an in depth explanation of the dp in question E? I understand the dp which would require O(n^3), since you can find the other coordinate via the manhaten distance, but I am struggling to grasp the dp that would require O(n^2) memory

I did problem C using set and I have

`n+m*log(n)`

time complexity,here is my submission.Anyway this is a interesting way to solve this problem and execution time is very near to the algorithm that work in`n+m`

time complexity.I am not able to understand why in problem B second variant probability is (n-c+1)/n . why it is not (c+1)/n .

If A is greater than the number of M, we are winning on any value from A to N.

PROBLEM 570C-REPLACEMENT

for the test case:

3 3

...

1 .

2 a

3 b

ans should be:

2

0

0

correct me if i am wrong

Where is the input string?

string was s= ...

Yes

F(...) = 2 (... -> .. -> .)

F(.a.) = 0 (.a.)

F(.ab) = 0 (.ab)

For the first hour, I ended up solving the wrong problem C. now I am curious how to approach this problem, If instead of replace the operation was of insert . How would be approach the problem. eg : s="..as..qwert...." first query is 1 h s'="h..as..qwert...."

Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.

Can someone explain the author's solution of the tree-requests, i am trying to understand the xor part of the code but couldn't find any explanations..Here the link to the author's solution-

http://codeforces.com/contest/570/submission/12523757

Can you perhaps provide more explanations in your solution to problem 570E? For example, what are stored in the array ou[dd][dd] and in[dd][2 * dd]? What is sotred in the array Si? Also, what does the variable ts represent?

Thank you!

ou[x][y] the position of the cell (x, y) on the diagonal.

in[x][y] the number and position of the diagonal of the coordinate cell.

http://codeforces.com/contest/570/submission/12779125 why this solution get WA15??

In D question, I did not understand the XOR part. Could someone explain me?

Hi.

Regarding Div.2 Problem C, I got WA on test 7 but it is very large.

Can anyone help me with some test case?

Here is my submission.

Problem D.I use technique similar to finding LCA,in order to find parent at i-th depth.But I have time limit,is this normal or the problem is in my code?code

Can anyone explain how the bit compression is used in problem D ?

In 570B Can anyone explain me the case when

nis odd and themis selected at middle of1tonrange. (Sayn=5 andm=3).Can't here we select bothn/2 andn/2+2 as answer fora?Could anyone explain in problem B 570B - Простая игра the case that are n = 1 and m = 1 , how the answer is 1 ,please ?? Although the problem says { The boys agreed that if m and a are located on the same distance from c, Misha wins.}

if you read the output section carefully you will notice that the problem say " If there are multiple such values, print the minimum of them."

so in your case you can choose any number because all numbers there probability is zero but the minimum one is "1".

570D Can also be done using DSU on trees. See this blog.

How do you use DSU on trees in this problem?

Yes. You can see this submission. If you understand the blog, it'll be easy to understand the solution. Do let me know if there's anything confusing in the code.

Got it. Thanks!

C-Replacement has a very simple solution Code : https://codeforces.com/contest/570/submission/81380215 Explaination: If a new . is added to a position i,(which currently has alphabet) there are 3 cases: 1. if it is causing merging of two groups-in that case i-1 and i+1 will also have . and f(s) will increase by 2. 2. if it is creating a new group-in that case i-1 and i+1 will have alphabets,and no change in f(s). 3. if it is adding to a current group-in that case either i-1 will have . or i+1 will have . but both i-1 and i+1 simultaneously don't have . , in that case f(s) increase by 1 Similarly,If a new alphabet is added in place of dot: if it breaks a group into two groups , f(s) decreases by 2 if it reduces length of a group f(s) decreases by 1 if it takes place of a single . (i.e. no dot is present on left or right) then no change

Can anyone check my submission for problem D? 91924931 I think it's

`O(nlog(n) + 26m)`

. Am I right? Thank you.Problem $$$E$$$ is a replica of this USACO problem. I guess the USACO problem is a little easier because you don't have to deal with annoying parity stuff, but it's still basically the same problem...

nice round