Before contest

Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

08:41:00

Register now »

Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

08:41:00

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | Petr | 3325 |

2 | OO0OOO00O0OOO0O0…O | 3289 |

3 | Um_nik | 3278 |

4 | Syloviaely | 3274 |

5 | tourist | 3206 |

6 | Radewoosh | 3197 |

7 | V--o_o--V | 3167 |

8 | mnbvmar | 3096 |

9 | dotorya | 3086 |

10 | FizzyDavid | 3023 |

# | User | Contrib. |
---|---|---|

1 | tourist | 183 |

2 | rng_58 | 168 |

3 | csacademy | 161 |

4 | Petr | 160 |

5 | lewin | 151 |

6 | Swistakk | 150 |

7 | matthew99 | 142 |

8 | BledDest | 141 |

9 | Errichto | 140 |

10 | adamant | 139 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2018 11:54:00 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

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 inO(n + q)?Hmm, links works strange...

Check Topcoder(https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#A%20O(N),%20O(1)%20algorithm%20for%20the%20restricted%20RMQ)

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.

link?

https://en.wikipedia.org/wiki/Gaussian_elimination

About Gaussian_elemination and how to derive the amount of solution according to the final matrix.

https://en.wikipedia.org/wiki/Transformation_matrix

As 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.

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".

the calculation rules are modified to suit the cyclic group.

for example, you want to do Gauss elimination on

then the step is(to make it easy to understand, I follow the method on wiki)

Which criteria are used to set division rules? More precisely, how do you calculate it?

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.

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 fromstofand Grisha rides fromttof, it is obvious thatcalc(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)?It can be proven, that when the tree is given as array

p_{2},p_{3}, ...,p_{n}, thenp_{i}is always a parent of vertexi, if we consider vertex 1 to be the root.Proof of this:

Consider the sequence

i,p_{i},p_{pi},p_{ppi}, .... By definition of thep'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, sop_{i}is closer to 1 thani.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

AREsome problems with regex implementation of GCC in CodeForces, see:TLE with VSC++(this is expected)

RE with GCC 14

RE with GCC 11

Down voted by mistake. :(

What is "lca" in the solution for D?

Lowest common ancestor

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/28858056

But even after acceptance, it took to me a lot of time to be convinced that it works in all cases.

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.

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/28865055in 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

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

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 betweenaandbthencalc(s,f,t) = (dist(s,f) +dist(f,t) -dist(s,t) + 1) / 2Implementation: 28875062

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

pbe outside of pathx-yif and only if we movepcloser toxstep by step and at every step it gets closer to bothxandy.You should consider 3 cases:

tis outside of paths-fand closer tosthanf,tis outside of paths-fand closer tofthansandtis not outside paths-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:

Note that the following expression uses floor division:

Lets= 3,f= 2,t= 4But 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 pathatob. So the formula works because.

Ah! Thanks for your advice. I missed that sentence in your post.

For problem D, since

sandtare 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 TLE

TLE 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 topcoder

Mainly, look at the

Sparse Tablesection.I think they assume that power and log operations are .

You can pre-calculate logs ans powers in .

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?

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

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 link

Can 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?

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 isO(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.

28978544

implementation 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:

we will get runtime error 30198318 Why is that? Why the second line must be

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?

deleted