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

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

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 30th edition will be held on 21th October 2015 at 16:30 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 me 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 after the contest.

Good luck and have fun!

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

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

Ideas for 3rd??

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

    Binary search on how big A[i]*B[i] will be almost before the end

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

      Can you be a little more specific?

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

        Maybe a piece of code.. #tdG8Iv

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

          Thanks!!!

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

          Was 5th some standard stuff or did I miss some key observation?

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

            Just a suffix automaton + Dijkstra...

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

              LOL.. thought of this but gave up just because it was 5th .....

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

              Can you please help me? I got 109 point with Trie & Dijsktra. Again got 106 with Suff. Automata (Here, 1 test case got TLE). Can't figure out why wrong answer. Please can you help regarding this problem?

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

              GOT AC.

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

          Is a priority queue really necessary in C? I think after finding 'max' in result array, the only a[i]'s that can be further decreased are the ones equal to that 'max' after decrease. So we can just process them serially from left to right in O(n) by a simple iteration keeping track whether further days are left or not.

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

          Hey adamant, why don't you sort according to the number of problems while computing the final result?

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

    Binary search for maximum value in result array. After this you have done most of k opeprations so k is small. For small k you can solve it using heap

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

How to solve "How Many Solvable Puzzles" I always get TLE

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

Was anyone able to use the criteria of solvability on wikipedia for a solution that does not TLE?

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

Any idea on how to solve Four Primes(2nd Question) ?

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

    Just find all primes that are less or equal than 8000, and use knapsack algorithm for this:
    d[i] = how many primes needed to find i
    so, if d[j] > 0 and d[j] < 4 (if we can find j, and we can find it with less than 4 primes) then
    d[j | prime[i]] = d[j] + 1 if this is a better solution.
    my code

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

My code for B: http://ideone.com/NPSnTu :D (it got full score)

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

    Okay. I am not able to figure out what rng.next(v.size()) does ?

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

      Well, rng is just a pseudo random number generator and rng.next(K) generates a number in range [0;K-1]. So what I do in order to check if the current number can be expressed as the "OR" of at most 4 numbers is the following. Having the prime numbers in a vector "primes", we can take those which can possibly be in the at most 4 numbers. A number P can be in those at most 4 numbers if A==(P|A) where A is the current number to be checked. Now, let's 8000 times take some randomly chosen 4 indices (not necessarily the same) and check with them :D

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

Screencast with music

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

How do you solve E with the maximum score? I could only get 85.72 by using Djikstra's algorithm.

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

    I have used the Suffix Automaton,then use Djikstra Dp(a,b) a-vertex,b-Automaton state.

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

      Well can you please explain why DP(a,b) with state b as suffix automaton work ?? I was thinking of DP(a,b) where b was the hash of the string formed till now i.e shotest path from 1 to a with b as the string formed but that would give tle as there are total n square possibilities of b.

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

When will the editorials be available?

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

By the way, what does %pic related% button do? I thought that Shortest Path Revisited was the fourth problem since it's exactly what I saw after I followed this link from the 3rd task: look at the bottom-left corner of the picture.

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

    I couldn't open the challenges page, so clicked "try next challenge" after solving the second one & got the hardest problem(shortest path revisited) as third -_-

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

Why doesn't hashing work in Shortest-path problem(Problem Link) ?Or it does and I did it wrong.

Here's what I did.

  1. Stored count of all pairs of (hash, substring_length) for all possible substrings of s.

  2. Stored 4 items in heap — (cur_distance, cur_node, cur_hash, cur_length).cur_length denotes the length of substring formed on reaching node cur_node from node 1.

  3. Applied Dijkstra.

But I'm getting only 85.71 points and wrong answer on many test cases.Here's my code.