Блог пользователя kevinsogo

Автор kevinsogo, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

And I planned to do round :D

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    When they decide to organize it :P

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      when do u decide to organize it. xD

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              What was ur idea to find period??

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

            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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

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