### Loud_Scream's blog

By Loud_Scream, history, 2 years ago, , Solution Arpa: 28852813

Solution Arpa: 28852764
Solution KAN: 28853440
Solution Arpa: 28853297
Solution Loud_Scream: 28853611 Tutorial of Codeforces Round #425 (Div. 2) Comments (77)
 » Can someone explain Ques B when the string contains '*' .Thank You!
•  » » if string(Say "str") contains '*' then it means that we can replace this '*' by another string(say "child_str") of any length (possibly 0). And this "child_str" must contain only bad characters(if it is not empty).Assuming it is possible to replace every '?' in "str" by a good character(because if it is not possible than answer is "NO") which is equal to the character at the corresponding position in query string, If you are able to form some child_str such that both the strings become equal then answer is "YES."
 » Has anyone written a solution for D with O(N + Q) complexity?
 » Sparse table works in O(n log n + q). How can D be solved in O(n + q)?
•  » » 2 years ago, # ^ | ← Rev. 2 →
•  » » » Oh, forgot about it, thanks.
•  » » Simply Farach-Colton and Bender algorithm :)
•  » » Or we can go offline and get O((n + q)α(n)) by Tarjan's algorithm.
 » Could you please provide further explanation for E or point out similar problems or tutorials for the required background?
•  » » It's just the basics of linear algebra. You can find it everywhere.
•  » » » » https://en.wikipedia.org/wiki/Gaussian_eliminationAbout Gaussian_elemination and how to derive the amount of solution according to the final matrix.https://en.wikipedia.org/wiki/Transformation_matrixAs we have to apply the transformation that we executed on the string matrix(it's like the LHS of an equation set)on to the b string(we can view it as the RHS), building a transformation matrix is faster and more visualized.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   Thank you, I am able to solve the system of equations but I am still trying to understand what things to be altered to the algorithm to work on "mod 5".
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   the calculation rules are modified to suit the cyclic group. such as 4+3=2 2*3=1 4/2=2 1/4=4 for example, you want to do Gauss elimination on 1 2 3 4 1 1 then the step is(to make it easy to understand, I follow the method on wiki) 4 1 1 1 2 3 to 1 4 4 1 2 3 to 1 4 4 0 3 4
•  » » » » » » » 2 years ago, # ^ | ← Rev. 5 →   Which criteria are used to set division rules? More precisely, how do you calculate it?
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   Division in a cyclic group is the reversion of multiplication. 4*4=1(mod 5) so 4*4=1 in a mod 5 cyclic group. moreover, as 5 is prime. Let P4={p|p=4(mod 5)}, P4 is the only set that for every p in P4, p*4=1(mod 5) So 4 is the only solution of 1/4 in a cyclic group. Well, maybe you should read something about Algebra Structures and you will find it easy to understand.
 » Why in D's solution, you just push back i into vector of p but not p into i's vector? And you said that we considered 3! = 6 permutations of a, b and c, but as I saw in the code, there was only 3 permutations. Correct me if I was misleading.
•  » » And you said that we considered 3! = 6 permutations of a, b and c, but as I saw in the code, there was only 3 permutations It's because editoral for this problem is written by me, but solution is by Arpa.Arpa, can you explain your solution?
•  » » » Hi. Sorry for the delay.Let calc(f, s, t) number of texts will be counted by Grisha if Misha rides from s to f and Grisha rides from t to f, it is obvious that calc(a, b, c) = calc(a, c, b).So we can use 3 permutations instead of 6.
•  » » We calculate the length of common part of paths from a to c and from b to c, so there is no sense in ordering vertices a and b, and we have only 3 variants for the third vertex.
•  » » » Thank you, I got it. But i read his code and i saw that he just do g[p].push_back(i) but not g[i].push_back(p) because as what I have learned, tree is bidirection graph, so we have to create 2 edge for each pair of vertices. And his dfs, I think if v is connected with u then we can only dfs(v) if v != parent(u)?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   It can be proven, that when the tree is given as array p2, p3, ..., pn, then pi is always a parent of vertex i, if we consider vertex 1 to be the root.
•  » » » » » Proof of this:Consider the sequence i, pi, ppi, pppi, .... By definition of the p's, each pair of consecutive vertices is distinct and connected to each other, so they must all be distinct (since trees don't have cycles). Then eventually this sequence hits 1 and ends, so pi is closer to 1 than i.
 » Anyone used regex to solve problem B. I tried using regex in C++ and hopefully generated the right regular expression pattern as well but couldn't pass the pretests. Can anyone help?
•  » » I got to test 79 with Python's Regex :-) 28858499
•  » » » My code gives right answer in ideone compiler for pretest 2 but when submitted here gave me wrong answer on pretest 2. This is really disheartening as I am not able to figure out the problem with my code. Any help is appreciated. 28850846
•  » » » » I have the same problem too. It works fine on ideone, but it fails the second pretest here.
•  » » » » Your submission is buggy when you copy reg to regi which is a uninitialized stack array, i.e. regi is not 0 terminated. I modified it a little bit to make it pass pretest 2. 28881236. However just like my previous submissions it fails at test 5 because of runtime error. I cannot figure out why
•  » » » » » Confirmed, there ARE some problems with regex implementation of GCC in CodeForces, see:TLE with VSC++(this is expected)RE with GCC 14RE with GCC 11
•  » » » » » » Down voted by mistake. :(
 » What is "lca" in the solution for D?
•  » »
 » 2 years ago, # | ← Rev. 3 →   I am not able to figure out any mistake in my submission. Can anyone tell what could be the mistake? Thanks. EDIT: solve(a, b, c) gives the answer to the common distance when you are going from b to a and c to a.
 » Is there a smaller test similar to test 6 for D?
 » My solution to C runs in linear time:http://codeforces.com/contest/832/submission/28858056But even after acceptance, it took to me a lot of time to be convinced that it works in all cases.
•  » » 2 years ago, # ^ | ← Rev. 2 →   Ugh, C isn't even conceptually hard, it's just extremely painful to code up.Honestly, I'm really tired of problems which are obvious binary searches on doubles with horrible implementations and high chance of floating-point error.
•  » » Sorry, I've found a counterexample to my solution to C (although it passes all tests). To simplify it, assume that the right-hand-side limit is L=76 instead of 1000000. Now, consider the input with n=3 people and s=4. person p1 looks left at x1=24, and v1=1. person p2 looks left at x2=28, and v2=3. person p3 looks right at x3=36, and v3=1. The right place for the bomb is x=x3=36, and it gives t=8.But my program is not going to find it.
 » I find lca for 3 stations and then understand that I am puzzled with many variants of their mutual location in tree..
 » Why ternary search on bomb position is not works? I think that function time(bomb_position) is decreasing and increasing then. http://codeforces.com/contest/832/submission/28865055
 » 2 years ago, # | ← Rev. 2 →   in C, i don't know how to apply scanline or prefix sum approach to find a point which is contained in both type(segments for persons going left & right) of segments can someone explain it or give link to read. what method is used in editorial? tia.
 » I really don't understand how to from the matrix,could you help me explaining the matrix. Forgive me my poor English.
 » Could anyone explain how to calculate the number of intersession edges for two given paths (problem D) please? I don't understand the formula given in tutorial.
•  » » Take a look at mraron's answer below
•  » » I also didnt understand formula in editorial so I made it up myself. Lets say you want to calculate commong edges of paths a->c and b->c.If level of lca( a,b ) is higher than max( lca(a,c), lca(b,c) ) that means a and b will meet up, and then together continue their path to lca( a,c) (in this case lca(a,c) == lca(b,c) ), and from there they will continue to b. So solution in this case is level[ lca(a,b) ] — level [ lca(a,c) ] + level[ b ] — level [ lca(a,c) ] , which is actually just level[ lca(a,b) ] — 2* level [ lca(a,c) ] + level[ b ]If level of lca( a,b) is not higher than max( lca(a,c) , lca(b,c)) , that means a and b will separately go to c, without meeting before reaching their lca's with b, so solution is level [ b ] — max( level[ lca(a,b) ] , level [ lca( c,b) ].So, you have 2 cases for 3 combinations of s,f,t : when s,f and t are destinations respectively. Code: http://codeforces.com/contest/832/submission/28877111
•  » » » 2 years ago, # ^ | ← Rev. 2 →   you made some typos when the destination is C (in formula above level[b] should be level[c]), but I understand you idea. Thank you very much for your reponse, it is very helpful. This is my understanding according to you reply. Consider also a -> c and b -> c, the idea is to see if a and b meet up before reaching max(level[lca(a, c), level[lca(b, c)]) (this is the point they will meet for sure). If yes we should add an additional length of level[lca(a, b)] — max(level[lca(a, c), level[lca(b, c)]). In general let la = level[c] - max(level[lca(a, c), level[lca(b, c)]) lb = level[lca(a, b)] - max(level[lca(a, c), level[lca(b, c)]) the answer should be ans = max(lb, 0) + la
•  » » » » Yes, thats it. Im glad I helped :) And yes, it should be level[c] instead of level[b], sorry for typo.
•  » » » » Thank you very much . It's very helpfull in order to understand it's idea.
 » Can someone please clarify what do (u1 & u2) represent in the Problem D explanation?
 » Simpler solution for problem D: let dist(a, b) be the number of vertices between a and b then calc(s, f, t) = (dist(s, f) + dist(f, t) - dist(s, t) + 1) / 2Implementation: 28875062
•  » » 2 years ago, # ^ | ← Rev. 6 →   thanks for it ...i have used this and my solution get accepted ...but can u please explain how you land on this expression?
•  » » » Let a point p be outside of path x - y if and only if we move p closer to x step by step and at every step it gets closer to both x and y.You should consider 3 cases: if t is outside of path s - f and closer to s than f, if t is outside of path s - f and closer to f than s and if t is not outside path s - f. If you draw all 3 cases you'll see why the formula is true.
•  » » You're a genius. This was the only solution I could understand :)
•  » » Counter example:Suppose we have the following graph:  1 / 2 / \ 3 4 Note that the following expression uses floor division:Let s = 3,  f = 2,  t = 4 But the answer in this case should be 1.Did I misunderstand your formula?
•  » » » Sorry my definition for dist(a, b) was a bit misleading and not well defined, dist(a, b) should be the number of nodes on path a to b. So the formula works because .
•  » » » » Ah! Thanks for your advice. I missed that sentence in your post.
•  » » Really clean solution. Thanks!
 » For problem D, since s and t are interchangeable, there are only 3 cases we need to check, not 3!. is the same as •  » » That is true! And since I used a slower lca method ( in such a way that my code complexity was ) checking only 3 instead of 3! possibilities made my code get AC instead of TLETLE code checking 3!AC code checking 3
 » How can you calculate the LCA in O(1) (I'm talking about problem D) can someone explain please ?
•  » » You use a sparse table, where the operation is just finding the max of two elements. Although it should be since you need to find the largest power of two less than a number. I guess this is negligible. Read about it more here on topcoderMainly, look at the Sparse Table section. I think they assume that power and log operations are .
•  » » » You can pre-calculate logs ans powers in . log = 0; for(int i = 2; i <= n; i++) log[i] = log[i >> 1] + 1; 
 » Note that number of edges in the interseption of two such ways v1 -> v2 и u1 -> u2, hv1 ≤ hv2, hu1 ≤ hu2 is max(0, hlca(u2, v2) - max(hv1, hu1)). Can somebody please show me how to prove this statement?
 » i didnt understand the matrix solE talks about, can somebody help me visualize?
 » 2 years ago, # | ← Rev. 2 →   For the problem B, How do I determine the length of matched characters for '*', if it is the beginning character? Should I go from backwards?
•  » » I have a simpler solution. It is easy to check '?'s and normal letters. Then calculate how many characters a '*' corresponds to (the final length has to be same) and check if those letters are bad. code: http://codeforces.com/contest/832/submission/28862633
 » 2 years ago, # | ← Rev. 3 →   How is the scanline approach in problem c (832C)? I have never heard of it and by googling I only found scanline for polygon filling as in this linkCan someone please explain to me if the above link shows the same scanline approach mentioned in the editorial, or where can I find a tutorial with the same "scanline" mentioned in the editorial (for segments intersections or so)? Is it like line sweep approach?
•  » » It means Sweepline.
 » Why problem E %5 is OK？
 » Could anyone explain what does that mean in problem B "It is guaranteed that the total length of all query strings is not greater than 10^5." Does it mean |S1|+|S2|+---+|Sn| <= 10^5?
•  » » Yes :)
 » Can someone please explain how do the prefix sums work in problem C?
•  » » 2 years ago, # ^ | ← Rev. 6 →   Your objective is to mark in an array (i.e. working in range [1,n] ) which places are suitable to put bomb in.For each person you get information about a new range [a,b] of the array that is suitable. The naive approach would be to iterate from a to b on the array and set all those items to 1. But it cost O(n) in worst case for person, that is O(n * m) overall where n is the amount of places and m is the amount of people.So to optimize you Just use an auxiliary array (name it sum[1,n]) and for each person that adds an a-b range you just increment sum[a]++ and sum[b+1]-- (the differences that would be in the final array). Note this cost O(1)With those information stored in sum[1,n] you can, after processing all people ,generate the real array with suitable positions with a simple formula in O(n)arr[i] = sum[i] if i = 1arr[i] = sum[i] + arr[i - 1] if i != 1There is a slight difference that in this case if arr[i] > 0 then the place is suitable, but the information we've generate is still useful.And the overall complexity of the process is O(m + n)
•  » » » Can you provide the implementation of this idea in a code? Thanks in advance.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   28978544implementation is terribly hard. I used binary search approach although there is a direct formula solution (that is even harder). Efficiency difference is slight in practice.
•  » » » » » Yeahhh..... I checked your code for this problem...and it was totally a bouncer for me...lol
 » I have a problem about C. If we change the compare function in the given solution 28853440 like: inline bool operator<(const tsob &a, const tsob &b) { if (a.x != b.x) return a.x < b.x; return a.t == OPEN; } we will get runtime error 30198318 Why is that? Why the second line must be return a.t == OPEN && b.t == CLOSE; I think this decrease the probability of swapping elements thus speeding the program up but without it I think we can still get the correct answer. I ran the code locally with a similar case to case 9, I indeed got segmentation fault. Anyone knows why?
 » 2 years ago, # | ← Rev. 3 →   deleted