wanbo's blog

HackerRank 101Hack 27th Edition
By wanbo, history, 9 years ago, In English

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 27th edition will be held on 23th July 2015 at 17:00 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.

Problems have been set by Devendra Agarwal and tested by wanbo. The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.

If anyone are interested in sharing their knowledge, you can comment in this post or send message to me directly. We eagerly need bunch of good problems.

Because the contest is intersected with the challenge phrase of SRM 663, we decide to postpone our contest for 0.5 hour.

Thank you HellKitsune for pointing this out. I have changed the contest time. You guys can have a good rest after SRM.

Good luck and have fun!

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

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Should be half an hour later, right now it intersects with the challenge phase of SRM 663.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I have changed the start time, now you can enjoy both contests, and have a good rest between them. Thank you for telling me the intersection.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah, intersection with Topcoder SRM 663 is quite unfortunate.

BTW, is there a way to click something on that countdown page and see my local time and date, when the event is going to happen? This would make it easier to add to calendar. Maybe I'm just blind :) ...

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

    I have changed the countdown to the fixed time, you can click the time directly to see the time at your location.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wanbo (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been trying to solve Special LCM of Subarray problem using Mo's algorithm. code, however I failed. Can't really understand what I've been doing wrong. Maybe, someone could explain me my mistake?

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

    Counter-example:

    6 1
3 3 2 5 2 5
1 4

    Answer is LCM(2, 5) = 10.

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

      Didn't get it though. We have L=1, R=4. Thus, S = {3, 3, 2, 5} and LCM(S) = 3 * 2 * 5 = 30. By taking it by modulo 3 we should 0. Why do you say the correct answer here is 10 though?

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

        We don't count 3 because it have 2 occurrences in our segment. Your task is to count LCM of all numbers having only 1 occurrence.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Oh, hell. I'm counting LCM of all numbers from given range when the task is to compute LCM of all single primes from the given range. Meh...

          Thanks anyway. I gave up contest, because decided there must be a problem in test cases :D Problem however was in my brain :D

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

      Why is this implementation wrong?

      thanks in advance :)

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    To correct your mistake, just replace this line
    ans[q[i].i] = answer * (1 — was_three);
    with this
    ans[q[i].i] = answer * (1 — (cnt[3] == 1));

    → Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

What's wrong with this solution for the last problem? I hope the idea is quite clear from the code.

→ Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Does anyone know where can I find editorials for 101 Hack contests?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

HOw to solve UNcompress String for full points ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Well, for every position i you can store cnt[i][j] which is number of times character j appeared in uncompressed s[1..i], along with size[i] which is the length of uncompressed s[1..i].
    After seeing that the answer for a query [L..R] is a difference between answer for [1..R] query and [1..L - 1] we are left with query "how many characters C present among first N characters of S?". If there is a i such that size[i] = N then we are done, you can simply output the corresponding value in cnt[][](you can find the leftmost position in size[] which is greater of equal to N with binary search). Otherwise you know that you've hit(with your binary search) a position where we had a digit(>1) in the compressed string.
    Let the position be P. We know that size[P] > N and size[P - 1] < N. We also know that uncompressed S[1..P - 1] was repeated some integer number of times. [1..N] fully contains S[1..P - 1] N / size[P - 1] (integer division) times. So we are left with a "tail" which is a prefix of S[1..P - 1] of length N % size[P - 1] and we can call the same function to count the "tail". Since we do calls only when we face digits > 1, the number of recursive calls will be at most log(1018) which is the maximum value we can be asked about.

    Hope the code will make it clear.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Do you solve problem D with some strange dp? I thougt about 5D dp, but I have some problem with base during the contest.

Nice tasks, only about texts I want to say something.You write everything in text but some important things was on bad places, so I spent a lot of time for understanding statements.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Three states: length, mask, pointer. Length is number of digits placed, mask is last 4 digits, pointer can be true / false. Pointer is true if we take a new placed digit (i.e. a[length + 1]) in our sum, and false if we skip this digit and take next one (i.e. a[length + 2]).

    Here is my code

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

      Thanks !

      I though about that solution, but I like to say 5D dp before mask ( it looks like something pro :D ). I don't have the third thing ( pointer) in my solution. I believe that we can do dp without it.

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

      I did (length,mask). If I'm placing 2, I jump to states with length+2 instead of length+1, and while I can place 1 or 2 after it, that just means checking if the next two sums aren't equal to the forbidden one.

      → Reply