kevinsogo's blog

101 Hack 50 — HackerRank
By kevinsogo, history, 8 years ago, In English

Hello Codeforces community,

I would like to invite you to join HackerRank's 101 Hack 50 on June 20, 2017.

There will be five tasks and three hours for you to solve them. The contest will be rated and the top ten contestants will receive HackerRank T-shirts!

The problems are prepared by kevinsogo, nabila_ahmed, zemen, fedimser, and krismaz and tested by shashank21j, allllekssssa, bayleef, wanbo, and kevinsogo. I hope you'll enjoy the problems prepared by the community!

Happy Coding!

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

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

And I planned to do round :D

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

just curious, when world codesprint 12 will be shown in contests??

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

    When they decide to organize it :P

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

      when do u decide to organize it. xD

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

        Well, I believe it most depends of zemen hard tasks :)

        I will try to prepare couple of problems for the next month ( I am waiting a lot of time, just need to finish exams), but it is not my decision if they will use on CodeSprint or not — I only can insist :D

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

How to solve C efficiently . I tried to brute force using string hashing . But I wasn't able to implement it in time . Anyways it would run in O(N3).

I don't want to spoil the solution by seeing the editorial , can someone give some hints.

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

    Think about the solution when you should remove some prefix of the string and insert it as a suffix. When will such operation leave the string unmodified?

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

      Is it anyway related to KMP where we need to find the largest prefix which is also the suffix ?

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

        Yes. Think in terms of rotation of a string. :)

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

          I understood the idea of euler totient function. But there was a approach O(s^2 *log(s)) for finding primtive periods of all substrings.Can you elaborate on it?

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

            I didn't use any of that. I just found the period of each substring (if it exists) and added (r-l+1)/p-1 to the answer, where substring range is [l, r] and p is period.

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

              What was ur idea to find period??

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

                We can basically find the period of any string ( primitive period ) using KMP.

                If the length of longest prefix that is also a suffix is 'x' and let 'n' be the length of the string, so the period is n-x if n%(n-x)==0.

                So in this question for string of length n, for each starting point l, we make a string from [l,n] and then compute the longest prefix array, which then gives us the period for range [l,r] where l<=r<=n.

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

                  Nice technique!!! THanks

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

              Can you share your implementation? I did exactly as you said and i get all the test cases right but i still get last 2 test cases somehow wrong and i tried everything including overflow , double hashes still no luck. @satyaki3794

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

          Can you please elaborate why is calculating the sum of total successful rotations of a substring the answer?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 3   Vote: I like it +1 Vote: I do not like it

            Consider the original string. Suppose you move the substring of length len, which started at index i. Now let the position of that substring in the final string be j. Notice that the part of the original string in the intervals [0, i-1] U [j+len, n-1] is unchanged, so you can completely ignore those.

            Consider only the part of the string in the range [i, j+len-1]. This is the part which is modified by the above operation. Observe that the above operation is in fact the rotation of this new string. You have chosen a prefix of length len and made it a suffix. But there is the added condition that the string should not change, i.e. you have to rotate it such that the final string is same as the first one. This is a well-known problem and it is known that to achieve that, the length of the moved string must be a multiple of the smallest period of the string.

            I think this is a similar problem.

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

    It also turns out a well optimized O(N3) can pass each case in under .2 seconds.

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

I got lucky... For D: Frog in Maze, I knew the solution was going to be

[intended solution]

but somehow I could use

[some other trick]

to simulate DP 2^20 rounds, squeezing within the time limit (1.95s/2s), and pass all the test cases. Also, simulating only ~10^4 rounds already gave me 60.51/65 points.

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

    Hey, can u plz explain ur solution using matrix powers? Also by simulating rounds, u mean to intialize exits by 1, rest by 0, and iterate over all about 10^4 no. of times, right?

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

      (Never mind the spoiler tag then.)

      1. Compute the transition probabilities X (i.e., X[p1][p2]: if you're at p1, what's the probability that you'll end up at p2 in one step). Nothing enters the obstacles or leaves the mines or exits.

      2. Compute Y = X^N (for some large N). Y[p1][p2] would be the probability that you'll end up at p2 after moving N steps from p1, including getting stuck at p2.

      3. Sum Y[start][exit] for all exit cells '%'.

      This method is only an approximation, but I was surprised it was good enough.

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

    Makes sense that it would work. The matrix equation to solve is (E - T)p = v, where E is the unit matrix and p are probabilities; informally, (geometric series), you're simulating just the first x terms. As long as all eigenvalues of T are less than 1 in abs. value, Tk should converge to the zero matrix (about as fast as ).

    → Reply