MikeMirzayanov's blog

By MikeMirzayanov, history, 4 years ago, translation, In English,

Welcome to 2016-2017 CT S03E07: Codeforces Trainings Season 3 Episode 7 - HackerEarth Problems Compilation. The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

Many thanks to Errichto for the preparation of the training. He has saved me!

Visit Codeforces::Gym to find the contest and register.

We are planning to start on October, 26, 2016 13:10 (UTC).

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

UPD: The training is over. Many thank to HackerEarth for problems! Undoubtedly Errichto is my hero of the day — he've prepared the training! Special thanks to the problem writers.

The editorial is in the comment http://codeforces.com/blog/entry/47985?#comment-322692


 
 
 
 
  • Vote: I like it
  • +86
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The registration starts 6 hours before the contest!! isn't that a short time to register?

»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Finally! It took too long to announce this one :(

»
4 years ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

Good luck for all

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

 I've just seen them on top1, and then...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    And then they got disqualified for searching problems in the Internet and copying all solutions.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem I prime moving ?

»
4 years ago, # |
Rev. 4   Vote: I like it +79 Vote: I do not like it

I want to thank HackerEarth for allowing us reusing the problems (also thanks to the setters!), and to thank Mike for carefully checking everything, so you could have a nice contest. You can enjoy amazing and detailed editorials mostly written by pkacprzak.

A — Yet Another Problem with Strings

C - Stickmen

D — Strange Queries

E — Bravebeart

F — GukiZ Height

H — Precise Shopping

You can see my codes for H (both should get AC but the latter one is faster):

slower AC
faster AC

-

I - Prime Moving

J — Valentina and the Gift Tree

K — The World of Trains

And congratulations to dans, HellKitsune and IlyaLos for winning the contest (after they were far behind in the first half of the contest). Nice job!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Time limit for problem A is very generous. It alows solution with complexity to pass.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      It was intended. What wasn't intended is that O(N·Q) passed, what was the combined results of: not all solutions uploaded in Polygon, weak tests and the fact that I wanted to let to pass, even though we didn't let it pass in the original contest a year ago, what I didn't remember (and unfortunately I marked this solution as AC in Polygon a year ago). If I knew that some O(Q·N) passes, I would cut TL significantly.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please answer me a question?

      I've thought up an idea that when adding a char after one of S , form a line just like a tail,and when the total length of the tails meets , rebuild the A.C Auto and its fail tree.

      I'd like to know whether it's right or what yours is.

      Thx.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Thank you! Somewhy we were mostly stuck on problems solved by significant amount of teams, wondering what are we missing, and came up with them only closer to the end of the contest.

    As about problem A, one of our state teams got AC with Aho-Corasick algorithm (offline!). We checked their solution and found that it's very unlikely to be true, so it seems that tests are not weak just about missed TLEs.

    Though maybe you can show us why it works, or maybe it can be modified to be online? We've found some other solutions with Aho-Corasick algo, but none of those were fine to us.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've got something puzzling about question A.

    I'd like to ask how it works to modify the fail tree of Aho-Corasick Auto when adding a new node after one of S.

    Or the solution doesn't depend on A.C Auto at all?

    But how to "know how many strings from S are prefixes of the string corresponding to this node"?(Please ignore the question above)

    And how to operate when it's necessary that "Next, if there is no node corresponding to Si with appended c, we create it and set up its counter"?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've the same question how to modify fail tree efficiently?? I tried one pass on all nodes with level one less than level of newly added character but got TLE.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In A's solution: "contains(t) := returns YES if at least one string from S is a prefix of string t. Otherwise returns NO". I though it was substring instead of prefix?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I was trying to understand what other teams did with problem A and I found a problem: you don't have tests with equal strings. I changed multiset to set and still got AC. If you have two equal strings (with equal hashes) and change one of them you somehow delete both of the hashes from the set and it should get WA. :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's exactly the meaning of substring in problem A?

Isn't it just to check if at least one of the given S strings is contained in the string deciphered from a query ? I can't really get it other way..

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice contest, and thanks for the fast editorial!

Also J was such a HLD bait in my opinion, hahah

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    "HLD is Heavy — Light Decomposition. Alot of code."

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve G?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I used inclusion exclusion.

    Say we have m numbers out of which we have to choose n numbers with repetition allowed, without any constraint, the number of ways is .

    Let x = P 1 P 2... P k, where P i = p i e i, where e i is exponent of p in x.

    Since x divides lcm( a 1, a 2, ... a n), each of P i divide at least one of a i. Let us remove cases where some of P i divide no a i.

    So lets choose a subset Q = {Q 1, Q 2, ...Q m} of P = {P 1, P 2, ... P k}. Let num(Q, a, b) denote the number of integers lying in [a, b], not divisible by any of Q i. Note that num(Q) can be found in O( m * 2 m) by inclusion exclusion again.

    The answer is

    Since we are considering subsets of subsets, the overall complexity is O( k3 k + n2 k)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone please DM me the code of Problem-D