Hello CodeForces Community!
I am glad to share that HackerRank's World Codesprint is scheduled on 29-January-2016 at 17:00 UTC. Contest duration is 24 hours.
Go ahead and register now to show off your coding abilities, and win upto $2000 Amazon gift cards/bitcoins, medals and tshirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.]
The contest is sponsored by Distil-networks, Pampared-chef and Philips. Contest site will be continually updated to reflect upcoming sponsors.
The problems were prepared by malcolm,Errichto,svanidz1, forthright48, and Shafaet. Thanks to wanbo for testing the problems.
The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.
Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.
Update: Scoring: 15-25-40-60-80-80-100-100. All the problems will have partial scoring unless explicitly mentioned in problem statement.
Update:
Contest is over. Congrats to the winners.
Hackerrank will contact the winners for prizes very soon! Please share your opinion on the contest in comments, it will help us to improve. The next contest is Hourrank, see you there!
What an intersection!
Both contests on cf and this one start at the same time!
Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.
Just mentioning this for the others because it's in the rules but not in the announcement. For me personally an Amazon Gift Card would be better, but I guess tough luck =)
You are right, I should've mentioned it. Added it in the post now, thanks.
Also, there is bad news for tourist.
Residences of the following countries and territories are not eligible to win prizes due to legal restrictions: Antarctica, Afghanistan, Cote D'ivoire, Cuba, Belarus, Bouvet Island, British Indian Ocean Territory, Cameroon, Central African Republic, Christmas Island, Equatorial Guinea, Haiti, Heard Island and Mcdonald Islands, Iran, Islamic Republic of Iraq, Democratic People's Republic of Korea (North Korea), Lao People's Democratic Republic (Laos), Lebanon, Liberia, Libyan Arab Jamahiriya, Myanmar, Nigeria, Pakistan, Papua New Guinea, Serbia and Montenegro, Sudan, Syrian Arab Republic, Zimbabwe.
tourist lives in russia.
Hi! Could you please explain the reasons of non-eligibility of Belarus residents?
Probably because you're an evul dictaytorship to some countries.
Has anybody received T-Shirts from the university world cup?
If you (or anyone else) haven't received it yet, please inbox me your hackerrank username and make sure your profile contains your address.
NOPE. I've sent multiple emails, no reply. The DHL website shows the same status since last few months.
Yes, i have received it dude :)
Yes, I have also recieved it, just before 2-3 days
Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
It's not a good idea to announce about HackerRank contest on CodeForces's website that conflict in start time with CodeForces round.
Well unlike codeforces they don't care about community.
Its not true that we don't care. We exist only because the community exist, not the opposite.
We re-scheduled our contest time because of conflicts several times and we will do so in future too. This time we couldn't do it due to many reasons.
Can you double check the test case of the last problem? It looks like lots of us are getting 46.67pts including tourist.
There was an issue with the tests. We fixed and rejudged it. We are extremely sorry for this.
(You now got full points.)
All right, I gave up on the contest after not being able to get the very first problem accepted. Now that's a bit disappointing.
I totally understand the disappointment :(. Still only 5 people got full score till now, I hope you will start again and end up in top 10.
Now I know how to stop you to solve the hardest task in 7 minutes :P
The test cases still seem weak. My first submission passes while it should not (test case "288 18").
I am very sorry for issues with the last problem. My program wasn't correct. Unfortunately, tester made the same mistake (without seeing my code).
I will write a few more words later today (there is the FHC in half an hour), to explain what I did wrong and how it could be avoided in the future. In short, I should have written a checker and consider the possibility that my outputs aren't optimal — then the checker should crash or something.
tourist, I apologize you as much as I apologize other contestants. Sometimes organizers make a mistake. I know I fucked up but it was your choice not to do other problems. It was reasonable (because likely one must solve all problems to get prizes) but it has a disadvantage that organizers' mistakes affect you terribly.
I'm sorry.
Where are the time limits, memory limits for the problems given ?
Check environment page.
Bear and Cryptography: precompute solutions for odd K (only powers of 2); for even K, keep decreasing N and factorising till it gives K factors. A very optimised
factorisation gives full score.
Build a String: O(N3) DP, various optimisations and bucketing of suffixes by the first two characters: 72/80 points.
Self-Driving Bus: adding vertices + union-find, O(N2) checking which intervals give valid answers. Once again, optimisations. If there's no chance of it running in time, try a stupid (but fast) guesstimate (4 tests passed this way, lol). 80+/100 points.
ヽ༼ຈل͜ຈ༽ﾉ
I got rank 270. Cool, congrats to everyone who won :D
I was wondering, how do you guys plan to send the gift cards? I mean, I don't have an Amazon Account associated to the email I use for HackerRank, is it possible to transfer the card to some other account/shifting it to bitcoin?
I don't have answer at this moment. You will get email. If I get the answer, I will let you know.
Last time I won an Amazon Gift Card from Hackerearth they mailed me a Claim Code. Could use it on any Amazon Account.
why "Current Rank" is not the same as the rank in the Leaderboard?
UP: ok, it takes some time to be updated
Rank 11 again. Whyyyyyyyyyyy?
Problem "Build a String" can be solved in O(N) using suffix automaton, and I think this approach is easier than author's.
Problem "Self-Driving Bus" has O(NlogN) solution with centroid decomposition, which is also easier than author's HLD.
Could you elaborate on these solutions? I thought about applying both techniques but discarded them because I couldn't figure out how to make them work.
As a side note, I had a slightly different
solution for "Self-Driving Bus". My solution relied on the fact than a connected segment of size x has x - 1 edges between its vertices. Checking this property for different left ends of the segment reduces to maintaining the number of zeros in an array subject to range sum updates. Code here: https://ideone.com/hVosff
Problem 1. We need to maintain the longest suffix which appears in the string somewhere before. We store it's starting index and respective state in the suffix automaton.
When we add a letter:
1) Extend SA with this letter.
2) We need to extend our suffix with this letter. So we follow suffix links from the current state until there's an edge by this letter.
3) Now we need to make sure our suffix doesn't intersect with its previous occurrence. To do that, in every SA state we need to know the first index where corresponding string ends (it's computed in constant time). While this index is greater than our suffix's starting index — we decrease suffix length by 1, or delete it's first letter. What this means in SA: if the length became not greater than length of state reached by link from current — we follow the link, otherwise we remain at the same state.
All checks are done in O(1) and in total we move some pointers not more that O(N) times.
Please elaborate why is it O(n) in total. I wrote same thing but the proof is not obvious for me.
Suffix length increases by at most one for each letter added and it can't go below 0, so in total it will decrease not more than N times.
What is the current state? Do you iterate every time from the longest state?
Of course not. We maintain the state corresponding to longest suffix that can be copied.
Well, I do iterate from the longest state :)
Problem 2. We have tree center and we need to know how many good intervals contain it. If it has index v, we'd try to add for example v - 1 to the interval. This means we also need to add all the numbers on the path from the center to node v - 1, but we're only interested in minimum and maximum. We're building continuous interval, so we need to add all nodes between those minimum and maximum, and it's like a transitive closure.
Now the solution:
1. Find the center and run dfs to find min and max for all reachable nodes.
2. Find transitive closure (update those min and max to final values after we add all nodes between min and max). Surprisingly, this is done with a couple of simple loops in O(N).
3. Run 3 pointers: decrease left interval border, and maintain minimum and maximum possible right interval border and count of possible right borders between them. We just need to sum up those counts for all left borders.
4. Remember that we split the graph in the center, so current part may not contain all the nodes, and once we get a gap in the interval that has nodes from another part — we stop.
For "Self-Driving Bus", I also thought about centroid decomposition at first. But then I realized, we can also use the center of an interval instead of the center of the tree. So my solution only have a quick-sort like algorithm with BFS.
I solved self driving bus with a segment tree with lazy propagation only. Here is the code: http://paste.ubuntu.com/14799263/ . It is way easier that hld or centroid decomposition.
Can you elaborate a little on it?
Basically we have to find the number of pairs [l,r], such that the number of edges (a,b) such that l<=a,b<=r equals r-l. This implies r = l + number of such edge. Say initially each nodes value is their number. So lets run a loop from 1 to n. each time pick all the edges that start with a previous node and ends at current node and increase the value of each nod from 1 to this edge's other end. Then count the the number of previous nodes with value equal to current node.
Can you prove that your solution for "Build a string" using suffix automaton works in O(N)?
How to do build string using suffix array by using binary search. I am unable to understand the tutorial. can someone explain?
dp[p] = min cost to build string s[0 .. p]
note: dp[p] >= dp[p — 1]
In order to compute dp[p] we have two cases: - p-th character is appended, cost = A + dp[p-1] - p-th character is pasted, this means there is point k splitting the string in two, s[0 .. k] and s[k+1 .. p], k can be found using binary search
How to check if s[k+1 .. p] is in s[0 .. k]? Using suffix array and longest common prefix table we can find two values L and R, L <= SA[k+1] <= R, these values represents all the occurrences of s[k+1, p] in s, this can be done using binary search, now we are interested in the leftmost suffix containing s[k+1, p], this can be done with segment tree.
The overall complexity is O(N * log^3(N)).
What array a[] contains in tutorial code. And how the author calculated suffix array? by using hashing or something