| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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!
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 ?
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.
For kth mean path problem,why when K<=500,the result distance is smaller than 20?
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.
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.
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)
You can see code by link such as: http://www.hackerearth.com/submission/5717113/
Thanks. This works, indeed. I was trying clicking on the submissions from the leaderboard. The link there is different and the code is not visible: https://www.hackerearth.com/october-clash-16/approximate/different-sums/submission/5717113/
Do you mind also explaining your approach?
I guess you can see my main idea of different-sums from above code easily.
I must say I get 1st place just since I'm luck. Firstly we can find sequence such like 1, n , 2, n-1, 3, ... is good. Because all consecutive sum of same even length are only two possible values.
Base on that, I guess a method by intuition: repermute 1,2,...,n by above transformation many times and choose the best result. It work very much(I totally don't know why). My other codes are all base on this method.
can the editorials be uploaded soon ?