### josdas's blog

By josdas, history, 3 years ago, translation, ,

570А — Elections

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

O(n * m)

Solutions

570B — Simple Game

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)

Solutions

570C — Replacement

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)

Solutions

570D — Tree Requests

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

Solutions

570E — Pig and Palindromes

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(n3) — time and O(n2) — memory

Solutions

•
• +44
•

 » 3 years ago, # |   +3 Auto comment: topic has been translated by josdas(original revision, translated revision, compare)
•  » » 3 years ago, # ^ |   0 thanks for Editorial :)))
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +26 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 , 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
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ |   0 It is a memorization technique.
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ |   0 Ok I solved it. Pretty easy to be honest, it's hard only at first.
•  » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 How do we check whether the letters form a palindrome? Iterating through all the elements in the range might get a TLE exception.
 » 3 years ago, # |   0 Please elaborate Problem E also.You have not explained very clearly?
•  » » 3 years ago, # ^ | ← Rev. 5 →   +42 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 : f(x1, y1, x2, y2) : if S[x1][y1] != S[x2][y2] : return 0 if x1 > x2 or y1 > y2 : return 0 // include the base case when have two neighbouring cells or single cell // if neighbouring cells have same value return 1 // else return 0 ans = 0 ans = ans + f(x1 + 1, y1, x2 - 1, y2) ans = ans + f(x1, y1 + 1, x2 - 1, y2) ans = ans + f(x1 + 1, y1, x2, y2 - 1) ans = ans + f(x1, y1 + 1, x2, y2 - 1) return ans 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! :'(
•  » » » 3 years ago, # ^ |   +3 thanks a lot :) this is so much clearer (y)
•  » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 can u tell me more clear how to find y2?
•  » » » » 3 years ago, # ^ |   0 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 getmoves = (n — x2) + (m — y2)So y2 = n + m — x2 — x1 — y1 + 2
•  » » » » » 3 years ago, # ^ |   0 thanks, now understand.
•  » » » 11 months ago, # ^ |   0 Can you explain the memory optimization part a bit more?? and give the code please?? Would be really helpful
 » 3 years ago, # |   +9 The problems were great, but these explanations are a bit lacking. Could you please explain the solutions in more detail?
 » 3 years ago, # |   0 Second problem was top!! Just shows how important boundary conditions are while testing. Lesson learnt.
 » 3 years ago, # |   +9 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
•  » » 3 years ago, # ^ |   0 I solved it with the same complexity but using binary indexed tree But this overkilles the problem alot in my opinionThis solution is the sane as before but without logn
 » 3 years ago, # |   +1 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
•  » » 3 years ago, # ^ |   0 I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578
•  » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +3 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.
•  » » » » 3 years ago, # ^ |   0 Oh, that's nice, thank you. Surely will use this trick next time.
•  » » » » 19 months ago, # ^ |   0 this idea can save a lot of time from a newbie's point of view,thankyou!! :)
•  » » 3 years ago, # ^ |   0 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
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Great, thanks, so simple :) AC 12522984
 » 3 years ago, # |   0 I am struggling with problem CCan anyone give me a simplified explanation to it?Thanks
•  » » 3 years ago, # ^ |   +10 Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.Imagine there k strings of consecutive dots of length L1, L2, ... Lk, 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.
•  » » » 3 years ago, # ^ |   0 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?
•  » » 3 years ago, # ^ |   0 Have a look at this comment. Comment Here...
•  » » 3 years ago, # ^ |   0 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]).
 » 3 years ago, # |   0 Auto comment: topic has been updated by josdas (previous revision, new revision, compare).
 » 3 years ago, # |   0 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!
 » 3 years ago, # |   0 Problem D : Beware, Even printf , scanf giving TLE ;( using fast I/O got ACCEPTED .
•  » » 3 years ago, # ^ |   0 Your solution O(m * log * 26 + n). It is close to time limit.
•  » » » 3 years ago, # ^ |   0 I know, My bad , this was the solution i cud get along.
 » 3 years ago, # |   0 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
 » 3 years ago, # | ← Rev. 8 →   0 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.
 » 3 years ago, # |   0 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 .
•  » » 3 years ago, # ^ |   0 If A is greater than the number of M, we are winning on any value from A to N.
 » 3 years ago, # | ← Rev. 2 →   0 PROBLEM 570C-REPLACEMENTfor the test case:3 3...1 .2 a3 bans should be:200correct me if i am wrong
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Where is the input string?
•  » » » 3 years ago, # ^ |   0 string was s= ...
•  » » 3 years ago, # ^ |   0 YesF(...) = 2 (... -> .. -> .)F(.a.) = 0 (.a.)F(.ab) = 0 (.ab)
 » 3 years ago, # |   0 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...."
•  » » 3 years ago, # ^ |   0 Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.
 » 3 years ago, # |   0 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
 » 3 years ago, # | ← Rev. 2 →   0 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!
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # | ← Rev. 3 →   0 http://codeforces.com/contest/570/submission/12779125 why this solution get WA15??
 » 3 years ago, # |   0 In D question, I did not understand the XOR part. Could someone explain me?
 » 3 years ago, # |   0 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.
 » 3 years ago, # |   0 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
 » 3 years ago, # |   0 Can anyone explain how the bit compression is used in problem D ?
 » 8 months ago, # |   0 In 570B Can anyone explain me the case when n is odd and the m is selected at middle of 1 to n range. (Say n=5 and m=3).Can't here we select both n/2 and n/2+2 as answer for a?