[HackerRank] EpicCode on 20th June / Awesome Prizes

9 years ago, # ^ |

+21

Since there are 8 challenges you will see a full spectrum of difficulty ranging from Div2 A,B to something really hard.

Since there is a prize on solving even 1 challenge, I think everyone should give a try and claim that.

→ Reply

9 years ago, # |

← Rev. 2 →

What are rules btw? couldn't find them on the contest page.

I mean scoring system, penalty system, feedback, etc.

→ Reply

9 years ago, # ^ |

I have updated it in the post. What do you mean by feedback?

→ Reply

9 years ago, # ^ |

I mean when you submit do you know final result for that submisiion like jn ACM?

→ Reply

9 years ago, # ^ |

Just simple feedback. You submit you get judged. You may submit any number of times, without any deductions in score.

→ Reply

9 years ago, # ^ |

Thanks for the information

→ Reply

ItsLastDay

9 years ago, # |

+31

Can't enter the contest: first the system proposed to register for round, now it keep saying 'Err. Looks like something went wrong.'

→ Reply

VastoLorde95

9 years ago, # ^ |

← Rev. 2 →

Same here

→ Reply

Junior94

9 years ago, # ^ |

Same here.

→ Reply

rtheman

9 years ago, # ^ |

Working now.

→ Reply

codechefsucks

9 years ago, # ^ |

dont think so :(

→ Reply

Alex7

9 years ago, # |

A lot of 404s

→ Reply

VastoLorde95

9 years ago, # ^ |

+11

Keep calm and press F5

→ Reply

9 years ago, # |

Keep calm for <=5 minutes, huge load. We're fixing it asap.

→ Reply

object_oriented_program

9 years ago, # |

24 hour contest we can relax a bit I think :P

→ Reply

LashaBukhnikashvili

9 years ago, # |

+14

Oh really ? can't load ?! when you are posting this entry EVERYWHERE it's impossible to participate on Hackerenk with 10k people (don't care minuses) sorry for my open position.

→ Reply

9 years ago, # |

-11

Website smooth and up in action, please continue coding :)

→ Reply

I_love_Captain_America

9 years ago, # ^ |

+26

I submitted 20 minutes ago, still processing.

→ Reply

codechefsucks

9 years ago, # |

+28

after seeing it so many times the python joke is not funny anymore

→ Reply

xorfire

9 years ago, # ^ |

I get these for a change.

→ Reply

anshkhanna7

9 years ago, # |

it is talking forever to process :(

→ Reply

SlavaSSU

9 years ago, # |

Tell me pls anyone where can i see Time/Memory limits?

→ Reply

9 years ago, # ^ |

hackerrank.com/environment
1 exception C/C++ is 1sec in most of challenges.

→ Reply

linjek

9 years ago, # |

i think that's not good idea to use time prior for same competitions

→ Reply

Al.Cash

9 years ago, # |

-35

This contest made me look deeper into segment trees then ever before.

→ Reply

9 years ago, # |

Was sqrt decomposition solution to problem square array? I was only getting 68/80 for this..

→ Reply

SlavaSSU

9 years ago, # ^ |

i got 80 using sqrt-decomposition.

also stupid sqrt-decomposition got 92(!!! O.o) on Set queries, but i submitted it after contest finished(

→ Reply

9 years ago, # ^ |

Can you share your code?

→ Reply

SlavaSSU

9 years ago, # ^ |

sure, but i think it's hard to read this code.

→ Reply

I_love_Captain_America

9 years ago, # ^ |

Can you explain the basic idea. I couldn't understand an optimal update strategy. My idea was to go for an offline method, but it timed out still.

→ Reply

fruwajacybyk

9 years ago, # ^ |

← Rev. 2 →

I guess all problems of this kind can be solved using segmenet tree or even fenwick tree. I solved it using segment tree.

When we add an interval [x, y] then in fact we add log(n) align intervals which corresponds to our nodes in segment tree. On each align interval [a, b] we add sth like (k + 1)(k + 2), (k + 2)(k + 3), ..., (k + (b - a) + 2)(k + (b - a) + 3).

We keep four numbers in each node:

sum of actual values on this interval
number of k mention above
sum of k mention above
sum of k² mention above

And we use lazy propagation. U can find similar task with good editorial here http://lbv-pc.blogspot.com/2012/11/rip-van-winkles-code.html

→ Reply

LashaBukhnikashvili

9 years ago, # ^ |

← Rev. 2 →

I solved it by Segment tree, {1 * 2, 2 * 3, 3 * 4, 4 * 5...} = {1, 3, 6, 10, 15...} * 2 = {1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ...} * 2

for each vertex in segment tree I save 3 value: first element,Difference,and difference of differences,here my code with easy "lazy propagation".

→ Reply

MarioYC

9 years ago, # ^ |

you can solve it with Fenwick tree by first calculating: sum(i = x to n) (x — i + 1) x (x — i + 2) , you will get a polynomial of degree 3, then you can use four BITs to heep all necessary information.

→ Reply

I_love_Hoang_Yen

9 years ago, # |

What is intended complexity of solution for "Set Queries"?

I tried sqrt decomposition with complexity O(N * sqrt(N) * log(N)) (with logN for Fenwick tree), but only manage to get 82 pts :(

→ Reply

kraskevich

9 years ago, # ^ |

I got a full score with the same time complexity(but in my solution the extra logarithm arises from a binary search). I know how to get rid of it, so O(N * sqrt(N)) is possible.

→ Reply

I_love_Hoang_Yen

9 years ago, # ^ |

Could you briefly explain your approach? I tried reading the editorial on Hackerrank, but it didn't make any sense as how to do solve the problem in O(N*sqrt)

→ Reply

kraskevich

9 years ago, # ^ |

+42

Something like that:

Let's call a set heavy if its size is larger than sqrt(N).
For each heavy set, we can precompute its intersection size with all other sets.
To add something to a light set, we iterate over all its elements and perform point updates. Then we need to make updates to heavy sets.
To get an answer for a light set, we iterate over all its elements and also take into account all heavy sets updates(using the precomputed intersections).
To add something to a heavy set, we update its add value.
Answering a query for a heavy set involves a summation of updates for other heavy sets and its internal sum value.
A range update is just a range update and some changes to heavy sets.
Answering a range query requires getting a sum of the range and adding all updates for heavy sets.

How to do it quickly? Precomputing intersections of heavy sets with all other sets allows to process a pair of sets in O(1). An intersection of a heavy set and a range can be found in O(1) using prefix sums(I used binary search here during the contest). Now the most important part: range sum and range updates. Instead of using a segment or a binary index tree, we will use an sqrt decomposition(by dividing the array into sqrt(N) blocks). It can handle point update and point sum queries in O(1)(it is necessary for processing light sets in O(sqrt(N))) and range update/sum in O(sqrt(N)).

→ Reply

HandIeNeeded

9 years ago, # ^ |

Almost the same here, but I tried different boundaries to divide subset into heavy and light, turns out 317 gets 82 pts and 200 gets 91 pts. Really interesting.

→ Reply

zeulb

9 years ago, # |

+26

So I coded five sqrt decomposition codes in a day, two on IPSC, three on EpicCode. That must be something right

→ Reply

9 years ago, # ^ |

Did you get away with all of them?

→ Reply

zeulb

9 years ago, # ^ |

← Rev. 2 →

Yep, except the one problem on IPSC, though I spend hours optimizing them

→ Reply

ItsLastDay

9 years ago, # |

Can't stop thinking about my sqrt-decompositions being too slow for HackerRank! That time limit always gets me. Nevertheless, problems were great, it was a pleasure to solve them.

By the way, when information about acquiring the prizes will be available? For instance, "$100 of Amazon credits" is puzzling me.

→ Reply

9 years ago, # ^ |

Roughly in <=2 weeks you will get an email about claiming AWS 100$.

→ Reply

k0st1a

9 years ago, # ^ |

← Rev. 2 →

+14

how companies select candidates for interviews? Any chance to get interview out of first 100 people? (namely I finished at 167 place)

→ Reply

CountZero

9 years ago, # ^ |

namely I finished at 167 place

I believe it doesn't really matter. They look for good CVs, not for exact places.

→ Reply

9 years ago, # ^ |

They will contact you on their own, position increases chances but there is no cutoff.

→ Reply

Al.Cash

9 years ago, # ^ |

I wrote to support already, but I think I may get an answer here faster.

I selected the checkbox to be contacted, but still get a message on top of the page saying:

"Click here and select the checkbox 'HackerRank can share my name and email address with contest sponsors' at the bottom of the page, to connect with 16 awesome companies offering exciting career opportunities."

→ Reply

Neodym

9 years ago, # |

When'll you send a T-shirt? That's important for me, cause I'm living in Russia, but I'll get rest in Belarus during summer.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Lio Se, Seoul, Korea, Republic of

Actually, they didn't send anything to Russia at all for a while

→ Reply

Neodym

9 years ago, # ^ |

← Rev. 2 →

-8

Do you mean that Hackerrank doesnt send anything to Russia?

→ Reply

9 years ago, # ^ |

+13

Well, I don't know current situation but that was true few months ago.

→ Reply

CountZero

9 years ago, # ^ |

+14

I was in top-100 in recent Indeed-smth challenge, and they didn't even asked for my postal address. Also no sign of $100 on AWS account.

→ Reply

LashaBukhnikashvili

9 years ago, # ^ |

← Rev. 2 →

+14

In indeed-prime challange I was in top-100,and they messaged me:

Congrats — Claim Your Prize!

and in message they are explaining their things about marketplace, nothing about prize :)

→ Reply

9 years ago, # ^ |

That will be in a separate email. We don't take address, but send you a link to claim T shirt.

→ Reply

gvaibhav21

9 years ago, # ^ |

← Rev. 3 →

Do we need to be "authorized to work in the US" to get the prize? (for indeed prime challenge)

→ Reply

9 years ago, # ^ |

No, prizes are irrespective of anything. You can be a student, a professional anything

→ Reply

gvaibhav21

9 years ago, # ^ |

It was mentioned in the rules for indeed prime challenge

→ Reply

9 years ago, # ^ |

Yeah Indeed was different.

→ Reply

9 years ago, # ^ |

There has been trouble sending Tshirt to Belarus and Russia. We try to resolve that by sending to any alternate contact in USA for example.
Will still try and find a solution to this problem.

→ Reply

mHuman

9 years ago, # ^ |

What about sending Tshirt to Ukraine?

→ Reply

9 years ago, # ^ |

that is possible.
Trouble is in Belarus, Russia, Argentina.

→ Reply

vitux

9 years ago, # ^ |

← Rev. 3 →

What kind of trouble do you have with sending T-shirts to Belarus? Few months ago I recieved T-Shirt from India (not hackerrank).

→ Reply

9 years ago, # ^ |

Our Vendor says it's not possible. I am trying to have different Vendor very soon and will ensure no one is missed out.

→ Reply

marat.snowbear

9 years ago, # |

← Rev. 2 →

+16

Can somebody give a hint on "Epic tree" problem. Editorial is not helpful, the only thing I got from it is that you need to split the query into "upper part" and "lower part" and use HLD for both. I figured it out myself that it makes sense to split query into two parts but I was unable to implement the second part using HLD. Namely I mean this part of the editorial:

Secondly, we need to update our Interval Tree 2 by using again our heavy light structure. But this time we increase the values of the nodes lying on the path between a and b by t * size[x]. ( x is any of the node in the path between a and b and size[x] keeps the number of nodes in the subtree of x, including x ) We can do this update in O((logN)²)

So I have two questions here. First — how would you make this update given that each node has it's own size and you need to sum the values multiplied by unique size for each node?

And secondly:

Secondly, by means of our update type on the Interval Tree 2, we can now just sum up all the nodes' values in the subtree of x. This will give us how the updates happened below x affect our answer. We can do this in O(logN)

Given you have a HLD which can answer sum queries on the path, how would you query "sum over subtree" then? My only idea is to put all HLD paths into same array in DFS order so that those branches in total will occupy a contiguous range in the array so you can use segment or Fenwick tree to sum things up. Looks a bit more complicated than the HLD I used to implement before, is it the intended solution here?

→ Reply

GaryYe

9 years ago, # ^ |

Instead of updating the nodes/subtrees on the path from a to b, we can do three separate updates. First and second start from a and b respectively, and finish at the root. The third one is similar but it starts from $\text{[math]}$ , and we update - 2t instead. For the "upper part" queries we must update all nodes on the path to the root, but for the "lower part" queries, we only need to remember how much it got updated with an integer f_i, and increase it by t or - 2t.

Denote P(u) as the sum we would get, if we walk from u to the root, and add the subtree sizes of each node we encounter . This is similar to the idea of prefix sums, and is needed for handling the "lower part" queries, as we are required to calculate the following sum for each query on the "lower part" of u:

$\text{[math]}$

Calculating this sum can be done with two segment trees storing P(v)·f_v and f_v respectively.

→ Reply

HandIeNeeded

9 years ago, # ^ |

← Rev. 3 →

HLD can answer the query over subtree, HLD is a DFS order, so all the node of a subtree occupy a continuous range(U already knew that :) ).

And for Ur second question, we update a segment on segment tree, we don't care about the size of each node in the segment, since we are adding the same value to all of them and we want the sum of a segment in segment tree. So we can store the sum of size of all the mode in a segment and the value we add to the segment, then we know the answer is sum of size multiply by sum of value.

→ Reply

Harun

9 years ago, # ^ |

+21

I am the setter of Epic Tree challenge. First, you are right about that part of editorial. I have tried to explain how to do such update with segment tree, but I could not manage to do it. It is hard to explain, but you can check my implementation. It is easier to understand in that way.

Secondly, When you traverse the tree with DFS you get an order of the tree. Let's call it DFS order. With DFS order you can do HLD. In the meantime you guarantee that all nodes in the subtree of node X has contiguous numbers. So you can easily query that subtree.

→ Reply