Um_nik's blog

October Clash '16
By Um_nik, history, 8 years ago, In English

Hello!

October Clash on HackerEarth has started and you have 23 more hours to go.

I am the author of this problemset and niyaznigmatul is a tester. I want to thank sivukhin who helped me a lot with preparation.

I hope you find the problems interesting and wish you good luck!

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

Comments Comments (10)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem : https://www.hackerearth.com/october-clash-16/algorithm/phi-phi-phi/

Standard way of calculating totient exceeds time limit on last 5 test cases. Also, I think with given memory constraints, sieve would not work. Is there a more efficient way of finding phi value or a property that simplifies the problem ?

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

    If you get all factors of an integer, you can calculate totient easily. So you can use Pollard's rho algorithm.

    If you have books Introduction to Algorithm, you can also find the algorithm in it.

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

      For kth mean path problem,why when K<=500,the result distance is smaller than 20?

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

        It's a obviously wrong method for solving that problem.

        For example: If there a line with twenty-one consecutive 1s and many 1000s, the distance will larger than 20.

        But I guess the author don't carefully avoid such a fake solution.

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

From last 2-3 contests, there has been a major delay in editorials of rounds at hackerearth, delay of editorials of such long contests(even 1 day long) ,completely spoils the motivation to upsolve them and feels like a time waste :/ . Editorials for even october clash have not been posted yet :| please see to it.

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

How did you approach the approximation problem? I started with a local search kind of approach, trying to swap numbers starting from the identity permutation, but it didn't bring any significant improvements. An approach that did work better than the identity permutation was a simple greedy which adds elements to the permutation sequentially: always pick the number which adds the smallest number of new sums (and pick the smallest such number, in case of ties). But this was too slow (O(N^3)). I tried to improve things using bit operations, or to consider fewer candidates at each step, but they didn't work well (e.g. considering fewer candidates improved the speed, but impacted the score negatively). In the end, I could only run this for N <= ~2500. And, anyway, this approach is still worse than the top solution (even for the cases where it's fast enough).

And another question: I noticed that when I click on the submission of any contestant (myself included) I cannot see the source code anymore (this wasn't happening in previous contests). Do you know why? Can this be fixed? (I want to look at the top solutions for the approximation problem)

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

can the editorials be uploaded soon ?

→ Reply