Hello Codeforces Community!!!
I invite you all to take part in HackerEarth's January Easy contest.The contest will be held on 1st January,2018 at 22:00 IST.
Problems have been set by me(shubhamgoyal__) and tested by MiteshAgrawal.We are grateful to HackerEarth admin prat33k for his help.
You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts).
Good luck and have fun.
UPDATE1: Close to 3 hours left in the contest.
UPDATE2: Contest has started.
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
Really excited for this one !
January Easy' 18 Bro!
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
hope some problems will also be "easy" for beginners !!!
Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).
What was the expected solution for Shubham and Subarrays ?
Hashing
Solution
Can you explain a bit more ? How are you making sure (x,y) and (y,x) are same ?
Suppose hash function for value x returns basex for some base.Then hash value for (x,y) would be basex + basey and hash value for (y,x) would be basey + basex.So you can see both arrays map to the same hash value.
Is there a particular reason you have chosen 127 and 129 as bases?
Also, why have we used two bases? Why not hashing using just one, and storing it?
You can choose any base of your choice as long as there are no collisions.The reason for choosing 2 bases is also to prevent collisions.
How do we know whether the collisions will happen or not?
I got 100 points even without using hash , tests are very weak. For the hash solution , just rolling hash this string (see code) for avoid mle =) if they are the same, they hash value will be the same.
In Shubham and tree — 1
How can answer for distinct costs can be zero for any node???
That's how: https://www.hackerearth.com/problem/algorithm/shubham-and-tree-1-1f374157/?scroll-id=comments-183-380040&scroll-trigger=inview#c130633
UPD: OK, the link might not work. But the tests 2 and 3 are incorrect, and the second test, for example, contains loops, it's easily seen if you try to download the test.
Hi,
We have updated the test-cases for this problem, and rejudged the required submissions. We apologise for the inconvenience caused.
We are looking into it.Sorry for the inconvenience.
Also, cases were pretty weak. Edge weights were so random that even printing subtree size for each node gives full score :(. Hope you take care of it next time (I did it the correct way btw)
code
I have a question that how many people will get T-Shirt? Only 3 or 100 people. actually I am new on hackerearth and only did this contest and ranked 80. can I got T-Shirt?
Hi,
We provide T-Shirts to the first 5 eligible participants. Better luck next time :)
So is it 5 or 3. be specific?
I guess I overkilled C with persistent trie.
Can you explain how did you solve using persistent trie ?
Sure.
For every index i, maintain a trie which has all the possible subarray sums in a[1..i]. Again iterate over i, and select j <= i. You have to find the value in the trie till j — 1 which gives maximum xor value with
. Do it for all 1 < j <= i.
How to do C??
Please have a look at the editorials.
Really bad issue with test cases, hoping for rejudging. First time that I won a contest. : )
We are looking into the matter.We will update everyone soon.
Hi,
We have rejudged the required submissions. We apologise if you faced any issue. Congratulations for the first rank :)