### Loud_Scream's blog

By Loud_Scream, history, 3 years ago,

Solution Arpa: 28852813

Solution Arpa: 28852764
Solution KAN: 28853440
Solution Arpa: 28853297
Solution Loud_Scream: 28853611

• +38

 » 3 years ago, # |   0 Can someone explain Ques B when the string contains '*' .Thank You!
•  » » 3 years ago, # ^ |   0 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."
 » 3 years ago, # |   +3 Has anyone written a solution for D with O(N + Q) complexity?
 » 3 years ago, # |   +1 Sparse table works in O(n log n + q). How can D be solved in O(n + q)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0
•  » » » 3 years ago, # ^ |   0 Oh, forgot about it, thanks.
•  » » 3 years ago, # ^ |   0 Simply Farach-Colton and Bender algorithm :)
•  » » 3 years ago, # ^ |   +3 Or we can go offline and get O((n + q)α(n)) by Tarjan's algorithm.
 » 3 years ago, # |   +17 Could you please provide further explanation for E or point out similar problems or tutorials for the required background?
•  » » 3 years ago, # ^ |   0 It's just the basics of linear algebra. You can find it everywhere.
•  » » » 3 years ago, # ^ |   0 link?
•  » » » » 3 years ago, # ^ |   +1 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.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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".
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » » » » 3 years ago, # ^ | ← Rev. 5 →   0 Which criteria are used to set division rules? More precisely, how do you calculate it?
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
 » 3 years ago, # |   +3 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.
•  » » 3 years ago, # ^ |   0 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?
•  » » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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)?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +10 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.
•  » » » » » 3 years ago, # ^ |   +1 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.
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   0 I got to test 79 with Python's Regex :-) 28858499
•  » » » 3 years ago, # ^ |   0 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
•  » » » » 3 years ago, # ^ |   0 I have the same problem too. It works fine on ideone, but it fails the second pretest here.
•  » » » » 3 years ago, # ^ |   +1 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
•  » » » » » 3 years ago, # ^ |   0 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
•  » » » » » » 3 years ago, # ^ |   0 Down voted by mistake. :(
 » 3 years ago, # |   0 What is "lca" in the solution for D?
•  » » 3 years ago, # ^ |   +3
 » 3 years ago, # | ← Rev. 3 →   0 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.
 » 3 years ago, # |   +4 Is there a smaller test similar to test 6 for D?
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +1 I find lca for 3 stations and then understand that I am puzzled with many variants of their mutual location in tree..
 » 3 years ago, # |   +6 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
 » 3 years ago, # | ← Rev. 2 →   0 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.
 » 3 years ago, # |   +3 I really don't understand how to from the matrix,could you help me explaining the matrix. Forgive me my poor English.
 » 3 years ago, # |   +6 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.
•  » » 3 years ago, # ^ |   +5 Take a look at mraron's answer below
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 3 years ago, # ^ |   0 Yes, thats it. Im glad I helped :) And yes, it should be level[c] instead of level[b], sorry for typo.
•  » » » » 3 years ago, # ^ |   0 Thank you very much . It's very helpfull in order to understand it's idea.
 » 3 years ago, # |   0 Can someone please clarify what do (u1 & u2) represent in the Problem D explanation?
 » 3 years ago, # |   +13 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
•  » » 3 years ago, # ^ | ← Rev. 6 →   0 thanks for it ...i have used this and my solution get accepted ...but can u please explain how you land on this expression?
•  » » » 3 years ago, # ^ |   +1 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.
•  » » 3 years ago, # ^ |   +1 You're a genius. This was the only solution I could understand :)
•  » » 3 years ago, # ^ |   +4 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?
•  » » » 3 years ago, # ^ |   0 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 .
•  » » » » 3 years ago, # ^ |   0 Ah! Thanks for your advice. I missed that sentence in your post.
•  » » 17 months ago, # ^ |   +8 Really clean solution. Thanks!
 » 3 years ago, # |   0 For problem D, since s and t are interchangeable, there are only 3 cases we need to check, not 3!. is the same as
•  » » 3 years ago, # ^ |   0 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
 » 3 years ago, # |   0 How can you calculate the LCA in O(1) (I'm talking about problem D) can someone explain please ?
•  » » 3 years ago, # ^ |   +3 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 .
•  » » » 3 years ago, # ^ |   0 You can pre-calculate logs ans powers in . log[1] = 0; for(int i = 2; i <= n; i++) log[i] = log[i >> 1] + 1; 
 » 3 years ago, # |   +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?
 » 3 years ago, # |   0 i didnt understand the matrix solE talks about, can somebody help me visualize?
 » 3 years ago, # | ← Rev. 2 →   0 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?
•  » » 3 years ago, # ^ |   0 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
 » 3 years ago, # | ← Rev. 3 →   0 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?
•  » » 3 years ago, # ^ |   0 It means Sweepline.
 » 3 years ago, # |   0 Why problem E %5 is OK？
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   0 Yes :)
 » 3 years ago, # |   0 Can someone please explain how do the prefix sums work in problem C?
•  » » 3 years ago, # ^ | ← Rev. 6 →   +3 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)
•  » » » 3 years ago, # ^ |   0 Can you provide the implementation of this idea in a code? Thanks in advance.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 3 years ago, # ^ |   0 Yeahhh..... I checked your code for this problem...and it was totally a bouncer for me...lol
 » 3 years ago, # |   0 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?
 » 3 years ago, # | ← Rev. 3 →   0 deleted
 » 5 months ago, # |   0 Hello, could you explain for me the formular in the question D? I find out that if for example u2 or v2 is the root of the tree then the h lca(u 2, v 2) = 0 but something wrong here I can find a such road such as its intersections are more than one node.$max(0, h lca(u 2, v 2) - max(h v 1, h u 1))$
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Deleted