HackerRank 101Hack 26th Edition

9 лет назад, # ^ |

← Rev. 2 →

+14

No more clash now ^_^

Day for CF Round 309 has been changed. 101 Hack will still happen at the announced time.

→ Ответить

Junior94

9 лет назад, # |

+19

Starts in a few hours.

→ Ответить

9 лет назад, # ^ |

+17

I love that you are looking forward to it. Hopefully you'll be able to enjoy the contest! I along with wanbo have given our best try to make a balanced and interesting problem set.

→ Ответить

Neodym

9 лет назад, # |

-12

first three are too boring to solve and last two are too hard to solve — this contest was so unlucky for me:(

→ Ответить

CherryTree

9 лет назад, # ^ |

-11

The first three are boring, but the last two are quite standard. Still I haven't managed to solve the fifth because I have spent too much time (about 40 mins) on the second problem lol.

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

Oh, at least I am not the only one :) I spend 50 minutes on 2nd, feel ashamed :)

In fact I don't agree with Neodym, I'd rather say that last 3 problems are boring (and standard), comparing to first two :)

→ Ответить

9 лет назад, # ^ |

I did not solve second one. Spent almost an hour on it... What is the idea behind? My code is here.

→ Ответить

9 лет назад, # ^ |

+13

I can explain what I did .please be patient :P A- rotating ball . B is ball thrown from origin.

First I tried sending ball B at t=0. I found position of ball b at time =R (time taken by ball to reach at the circumference with thrown at time =0) if this position was in the first quadrant. Then optimal answer would be the one we get by throwing the ball B at t=0 answer in this was would be "R R%S/ gcd(R%S,S) / S/GCD(R%S,S).
if position of ball B at t=R is not in the first quadrant then answer would be "(r/s + (r%s):1?0)*s 0/1" because he can wait for some time t>0 and then throw the ball such that it collided at R,0

→ Ответить

9 лет назад, # |

What's wrong with this approach for 2nd : - r=r%s. if(r belongs to 0..s/4) print r/gcd(r,s) "/" s/gcd(r,s) - otherwise print 0/1 explanation : if r through at t=0 can reach a place in the first quadrant than do so . otherwise it can r,0 point in the next cycle

→ Ответить

9 лет назад, # ^ |

lets have a good laugh shall we :P .For 2nd I though the answer was of for "testcase_number fraction" :P XD

→ Ответить

ayush_awasthi

9 лет назад, # |

editorials?

→ Ответить

9 лет назад, # ^ |

See the update2. They have been enabled.

→ Ответить

arkahjp

9 лет назад, # ^ |

I am kinda new in hackerrank and could not find the editorials.

Can you(/anyone) tell me how can I find them?

→ Ответить

dreamoon_love_AA

9 лет назад, # ^ |

← Rev. 2 →

+25

kerker

→ Ответить

arkahjp

9 лет назад, # ^ |

thanks bro.

→ Ответить

9 лет назад, # |

Almost did task no.4. Suffix-Array + Lcp + Fenwick tree + Mo's algorithm. code However, getting TL... :(

→ Ответить

vitux

9 лет назад, # ^ |

Suffix-Array + lcp is enough.

→ Ответить

9 лет назад, # ^ |

+16

My solution was an overkill. I used suffix+lcp+2seg trees.
Can you explain your solution?

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

In fact it is not that bad, I would not call it an overkill. Constraints are loyal, so I did the same, but using hashes.

With hashes you can compare two substrings in O(1), this gives you LCP with bin.search only, this gives you SufArray with "LCP+comparing next char" comparator; and instead of using seg.tree of pairs / two seg.trees you may use two Fenwick trees, and code becomes even simpler.

→ Ответить

vitux

9 лет назад, # ^ |

← Rev. 4 →

+30

For each index i lets find such f[i], that s[i..f[i]] is unique substring, and s[i..f[i] - 1] is not. That can be done in $\text{[math]}$ using suffix-array and lcp. Note, that f[i] is non-decreasing sequence. Really, s[i + 1..f[i] - 1] is substring of s[i..f[i] - 1], so it is non-unique.

Now, for each query we can answer in $\text{[math]}$ : we'll find first segment i..f[i], which intersects with r, let it be q (q=upper_bound(f, r)). Now it's easy to count number of non-unique subsequences in s[l..r]: it's $\text{[math]}$ . That's because for all indicies x < q: f[x] < r, and for indicies x > q: f[x] > = r.

May be I missed + 1 or - 1 somewhere, but I hope that you can get the idea.

→ Ответить

9 лет назад, # ^ |

← Rev. 4 →

Thanks, nice solution.

→ Ответить

9 лет назад, # ^ |

Haven't figure out it during contest... can you help me with it?

→ Ответить

HandIeNeeded

9 лет назад, # ^ |

SA + MO works fine.

→ Ответить

9 лет назад, # ^ |

I did Suffix-Array + Lcp + Fenwick tree + Mo's. :) but getting TL sometimes. Can you share your code?

→ Ответить

9 лет назад, # ^ |

← Rev. 4 →

So, O(Nlog²N) and $\text{[math]}$ were supposed to pass, probably your solution has an extra O(logN) factor?

→ Ответить

9 лет назад, # ^ |

yep, it does :(

→ Ответить

HandIeNeeded

9 лет назад, # ^ |

Code

→ Ответить

1e9

9 лет назад, # |

Is there any problem in using Math.floor(1 + Math.log10(number)) to get the digit length? My one test case failed in 3rd question due to that.

→ Ответить

akulsareen

9 лет назад, # |

Is there any edge case in 5th question? I got a seg fault on 3 test cases.

→ Ответить

anuraganand

9 лет назад, # ^ |

I think it may be due to recursion depth. One of such test cases was a linear graph.

→ Ответить

9 лет назад, # ^ |

Stack limit is around 10⁶. So, I think there might be some other issue.

→ Ответить

9 лет назад, # |

For 3rd what should be the output for 1 53959375 29374943

→ Ответить

Kvark161

9 лет назад, # ^ |

79999999

→ Ответить

Sumeet.Varma

9 лет назад, # |

← Rev. 4 →

+14

It is just me or everyone felt that 3rd was quite easier than 2nd ? :P

Edit : I did it with O(17) ad-hoc solution per test case.

→ Ответить

sgtlaugh

9 лет назад, # ^ |

The 3rd problem was indeed a piece of cake with DP.

→ Ответить