Hi everyone :) ! I choose some problems from CODEFORCES and TIMUS.I invite you to participate in this contest.I will be glad if you join this contest :) http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38811#overview

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

1 | tourist | 3764 |

2 | slime | 3592 |

3 | maroonrk | 3535 |

4 | Benq | 3513 |

5 | jiangly | 3509 |

6 | ecnerwala | 3508 |

7 | MiracleFaFa | 3466 |

8 | ksun48 | 3452 |

9 | Um_nik | 3426 |

10 | greenheadstrange | 3393 |

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

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 183 |

4 | YouKn0wWho | 182 |

5 | Um_nik | 181 |

6 | antontrygubO_o | 173 |

7 | maroonrk | 168 |

8 | errorgorn | 165 |

8 | SecondThread | 165 |

10 | kostka | 164 |

Hi everyone :) ! I choose some problems from CODEFORCES and TIMUS.I invite you to participate in this contest.I will be glad if you join this contest :) http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38811#overview

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2022 15:10:24 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can we write solution of "Problem U(Line Painting)" with segment tree ???

Yes, you can. A simple, straighforward approach.

Regarding to Problem U(Line Painting) Could you explain solution with more detail? Thank you beforehand.

I thought but i didn't find solution. Could you explain solution of this problem please?

Compress coordinates to at most [0..2N). Build a segment tree over them; one query is a range update (set color of range) on it. Convert the result into an array, find consecutive white segments in it and (remembering how the coordinates were compressed) choose the longest one. Time: . It's really just about knowing the data structure.

Of course, a bruteforce instead of a segment tree (but with coordinate compression) would also pass.

Who think we can use KMP in "Problem D(Newspaper Headline)"? I think we can do this problem with KMP.But i dont 100 % believe...

It's about a subsequence, not a substring, so no KMP here.

The problems there are all easy, they can be solved without any serious algorithms. D is just about optimizing the straightforward LCS-like solution.

I don't know how you would like to use KMP, but I think it could be too slow if both strings are very long and the output is very big. (e.g.: s1="abbb...bbb", s2="aaa...aaa"). I thing KMP have O(|s1|*|s2|) complexity in this input because the shortest string which met the requirements have that much character.

"Problem J(Lucky Numbers)" solve with bitwise operation...

How can i solve Anansi's Cobweb(Timus)? here is link to problem http://acm.timus.ru/problem.aspx?space=1&num=1671. Thanks beforehand

The best approach is union-find on the operations in reverse order.

thanks, i got AC :)

can you elaborate it. i could not find solution for this problem anywhere.

finally i solved it

Apply the union operations(M) which are not in Q(coz those threats won't be removed even after Q operations) , then do the operations Q in reverse order ,

Could someone send the code of problem U(Line Painting)?