June 101 Hack on HackerRank

9 years ago, # |

+70

The problem set is in very high quality, I like it very much. And it is relatively a little harder than previous contests.

→ Reply

9 years ago, # |

+64

Guys, the contest starts in one hour. Don't miss it!

→ Reply

wannabe_khiladi

9 years ago, # |

-8

The site is down -__- :/

→ Reply

9 years ago, # |

+70

LOL an epoch time bug post-contest xD

→ Reply

9 years ago, # |

It's a pity that in last problem both cubic and quadratic solutions give the same number of points

→ Reply

9 years ago, # ^ |

You've got too great cubic solution, mine received only 27.50 points. BTW, good problems, but I've seen something similar to D in some Petrozavodsk training camp.

→ Reply

9 years ago, # ^ |

Yeah, that was a pity to see cubic solutions getting ~50 pt. Author's cubic solution is much slower and gets ~25 pt, as expected.

→ Reply

9 years ago, # ^ |

Well, setting n<= 5000 for quadratic solution would probably help, 1000^3/6 is not undoable :)

Thanks for good problemset

→ Reply

anshkhanna7

9 years ago, # |

How to solve the third problem?

→ Reply

9 years ago, # ^ |

You may find the solution in the "editorial" tab on HackerRank.

→ Reply

9 years ago, # ^ |

← Rev. 3 →

+19

By the way, did you came up only with a solution which finds the k-th element but not the whole array, or intentionally make this problem slightly easier?

→ Reply

Deemo

9 years ago, # ^ |

How do you find the whole array!?

→ Reply

9 years ago, # ^ |

I have no idea, how to find the whole array. Could you briefly describe your solution?

→ Reply

9 years ago, # ^ |

← Rev. 3 →

+29

At first find for every segment [l_i;r_i] the sequence of segments [l_i, r_i], [l_j₀, r_j₀], [l_j₁, r_j₁], ..., [l_{j_k}, r_{j_k}] such that i < j₀ < j₁ < ... < j_k, $\text{[math]}$ and l_{j_k} is minimal possible. This can be done by segment tree by processing the segments in reverse order (we need only the value of l_{j_k}).

Then for each position pos find the minimal such l_{j_k} for all [l_i, r_i] containing pos. Then process a_pos in the order of increasing a_pos, the position of it will be the first free positon after such l_{j_k}.

→ Reply

xxTastyHypeBeast666xx

9 years ago, # ^ |

+51

I must misunderstand what you mean..

Say you have initial array 10 11 12 0 1 with the segments 2 4 and 0 2.

Then from what I understand, for any position in the array, we find l_{j_k} = 0? But then we'd conclude that value 0 goes to position 0, then value 1 goes to position 1, but really it will go to position 3.

→ Reply

9 years ago, # ^ |

+56

It seems you are right, and my solution is a bullshit =) The tests were not strong enough :)

→ Reply

brucewayne123

9 years ago, # |

https://www.hackerrank.com/contests/101hack38/challenges/sorted-subsegments can anybody suggest an alternate approach to solve this problem?? the one described in editorial was like magic to me.. any intuitive approach by anyone please??

→ Reply

9 years ago, # |

+19

It was also a pity that in the third problem brute force in java (sort each sub-segment) got > 72 pts...

→ Reply

shas19

9 years ago, # ^ |

In c++ it only gave 20 pts, Why is that?

→ Reply

Deemo

9 years ago, # ^ |

That can't be true!

→ Reply

https://www.hackerrank.com/rest/contests/101hack38/challenges/sorted-subsegments/hackers/ankurverma1994/download_solution

9 years ago, # ^ |

→ Reply

javacoder1

9 years ago, # ^ |

Can you share why binary search is valid. The editorial explains little about this.

→ Reply

9 years ago, # ^ |

I'm not sure I've understood your concern.

We ask if value v at position k after Q queries is >= x. If that is true, then it is also true that v > x-1, x-2, .., 1. Hence the binary search is valid.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Agreed. Naive solutions using built-in sorts should NOT be worth > 90% credit. That was ridiculous and one of the major defects of this contest.

Furthermore, the very same naive solution in C++ only gave 20 points compared to java's 72. That's also a very, very interesting outcome. What are the underlying implementation differences between the builtin sort functions of the two languages, and are those differences (if any) accountable for the massive runtime difference? If not, is there some other factor that I'm not seeing here (other than I/O which I believe is a trivial factor given the low input constraints)?

→ Reply

9 years ago, # ^ |

+40

In java8 sort is TimSort which works good for almost sorted segments

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+10

:'(

i cri evrytim (pun intended)

→ Reply

9 years ago, # ^ |

We do not know Java's sort method is so fast for almost sorted array, the c++ solution only got 20+ pts. https://www.hackerrank.com/contests/101hack38/challenges/sorted-subsegments/submissions/code/6063903

→ Reply

bharsi

9 years ago, # ^ |

← Rev. 2 →

Another naive solution that gives high score of 67.10

Code

int main()
{
	//readf
	int n , q , k;
	ui min = -1 , max = 0;
	scanf("%d %d %d" , &n , &q , &k);
	long* a = new long[n];
	long inp0 , inp1;
	fo(y , n)scanf("%ld" , &a[y]);
	fo(y , q)
	{
		scanf("%ld %ld" , &inp0 , &inp1);
		if(inp0<min)
			min = inp0;
		if(inp1>max)
			max = inp1;
	}
	sort(a+min , a+max+1);
	printf("%ld" , a[k]);
}

→ Reply

9 years ago, # ^ |

+17

It's not naive — it's incorrect one :/

→ Reply

rhezo

9 years ago, # |

+11

Nice editorial of third problem. Thanks! But isn't the complexity O(Q·(log(N))²) instead of O(N·(log(N))²) ?

→ Reply

anh1l1ator

9 years ago, # |

One thing that I really don't like about hacker rank is that only 480 people had correct solution and yet my rank is 779.

That makes me not care about hacker rank rating . They always have a different and nice kind of problem set but these little things, I don't like them.
On the other hand it allows some people who know a concept to good extent might get some edge over other , there won't be a binary game , but this is often mis-used.

IMO constraints must be set such that only solutions with very good knowledge gets some points.

→ Reply

9 years ago, # ^ |

Well,

It's all about testing. They can add the number of test cases to solve per run. This way even to get a partial score, your solution would have to be correct.

Also they can exclude some edge cases if they want to provide partial score for not covering all the cases.

Anyway — the partial score system is more fair in my opinion. You do your best on all the problems and if you have a small bug or you miss one case, you can still get decent credits.

It also allows you to develop a better strategy to get a higher rank. You can decide whether you will try to spend more time on solving some problem completely or maybe it is better, to write a brute force and move on to the next task.

→ Reply

9 years ago, # ^ |

+10

I'd say that the partial score system actually isn't very fair, in some cases.

Try submitting a program that only prints 1 to the last problem, "Byteland Itinerary". Because you pass a few test cases with that, you get 4 whole points.

For example...

Consider person A, who solved the first two questions very quickly but doesn't know how to solve the rest. Person A gets 50 points and is very much ahead of other 50 point people because he solved them more quickly.

Person B takes forever to solve the first two, gets 50 points, and then submits a print 1 program to the last problem, netting a total of 54 points, and beating person A.

Person B doesn't deserve to be ahead of person A. This is where HackerRank's partial credit grading system fails.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Well,

They could add T — the number of test cases to solve.

Then they could add 10 small tests with different answers and printing 1 wouldn't score anything — as I said it is all about testing.

They have a big potential of preparing such a set of tests which will give different scores for different approaches. It is not the problem of partial scoring, but testing.

Anybody who has an idea which will get positive score on any task should get the higher position than somebody who has no idea at all. The fact how easy will it be, to get that partial score depends only on the tests.

→ Reply

9 years ago, # ^ |

-10

Good points.

I think the best way to rectify the issue I mentioned earlier is to only allow judge submissions if and only if the sample tests pass successfully (hackerrank's run tests button). Also, the sample tests should not be included for grading towards actual points.

→ Reply

sgtlaugh

9 years ago, # ^ |

+15

That's not a solution, one can simply write a couple more if/else statements to pass the sample. Adding some number of test cases as mentioned above is the only way I can think of.

→ Reply

MazzForces

9 years ago, # ^ |

+21

In a partial scoring system, the best solution according me is to have subtasks and not marks per test case. For example a person solving a smaller subtask should get full marks for that subtask if they solve it completely otherwise 0. This individual mark per test case actually rewards you for wrong solutions.A smaller subtask, ensures that a person has atleast solved the problem 100% for those particular constraints.

→ Reply

gvaibhav21

9 years ago, # ^ |

+32

The most unfair thing IMO about partial scoring is that the range of possible points a solution can get is continuous. This means that some optimisations like reducing constant factor of solution can make some tests of higher subtask pass, and award more points for almost the same solution.

For more complicated problems/codes, it then becomes a matter of chance which subtasks marginally pass/fail for which user. You can already see the wide variety of naive/wrong solutions for sorted-subsegments which got >=45 points. Different users might get a large variety of scores, with only a few users with partial solutions getting equal scores, and it beats the purpose of time-based penalty. This could be observed in this contest's ranklist as well.

This can be avoided by awarding subtask-based points (like is done in Codechef Long).

Also, i don't see any point in awarding even a small number of points for a very naive brute solution for the difficult tasks.

→ Reply

allllekssssa

9 years ago, # ^ |

I didn't do contest, but I prepared several rounds for HackerRank and have good experience with all this 'problems'.

My opinion partial scoring is better option and contest is more interesting. One thing which irritate me that nobody writes subtasks in the text (constraints + amount of score ). I am always trying to do it and think it is more fair. I saw comment that little optimisation gives more points, I think that is good, everyone has full feedback and can write such code !

One bad thing is that HackerRank doesn't have classical option for subtasks ( all testcases in subtask must pass for non-zero score) like Codechef. Normally we can put more examples in one testcase , but it is not always possible.

I am writting 2-3 solutions for my tasks and try to make optimal score for each, but sometimes it takes 5-6 hours, or even the whole day! I understand when someone can not do it on such way, also again it is possible to have mistakes like this Java sort...

About forum, I don't like that! I can not allow disscussing about tasks on that way. For me much better option is asking question to organizators and allow forum after contest finsh — or checking comments before posting it on forum by admin or setter.

I like quality of HR tasks in last months, for me that contests are the most interesting and often I am happy after my performance there, but for sure there are several things which guys from HR must do if they want community like CF :)

→ Reply

https://www.hackerrank.com/contests/101hack38/challenges/points-on-a-line/forum/comments/145470

9 years ago, # |

← Rev. 2 →

+66

And it was also a pity that organizers were giving hints to some contestants during the contest:

I don't understand such a behavior. If you wanted everyone to pass the first problem, you could have asked to print 1 for example.

Otherwise it is unfair for other contestants who didn't think of reading discussions during the contest.

Edit: That comment is just explaining the solution... https://www.hackerrank.com/contests/101hack38/challenges/points-on-a-line/forum/comments/145418

→ Reply

9 years ago, # ^ |

Because there are hundreds of very beginners in our platform, they do not have any experience in problem solving, we hope we can guide them to get their first AC. This is only permitted for the 1st challenge.

If just output 1, very beginners will also feel so stupid. Hope you can understand, there are hundreds of people still not passed even at the ends of the contest, and they will email to us complain about it. So we changed our strategy that we need to help them during the contest for the first challenge.

Everyone will be excited by their first AC, maybe because of these, several years days, they will be red coders. :) Someone with weak mind will may leave because of too many WAs even they are convicted that their solution is correct.

→ Reply

wrdsaj

9 years ago, # ^ |

+46

... there are hundreds of people still not passed even at the ends of the contest, and they will email to us complain about it.

So the lesson is: if you are lazy as fuck to improve, then complain about being lazy as fuck and get a free AC. Maybe that's the reason why there's a bunch of indian competitive programmers but only a few have decent skills.

→ Reply

memset123

9 years ago, # ^ |

← Rev. 2 →

+20

Chill, dude.

BTW I think you're going to need some burn heal.

→ Reply

wrdsaj

9 years ago, # ^ |

← Rev. 3 →

I'm just saying that if you are lazy to improve, accept your position and don't complain. But asking for hints during a contest is just stupid.

And if you feel offended for what I said about the indians, then read wanbo's comment. If there are hundreds of guys not able to solve an easy problem and only worried about getting an AC during contest, what can you expect from them in the future? Nothing, because they probably just don't even care about competitive programming and do contests only to improve her resumes or to pass a job interview.

→ Reply

allllekssssa

9 years ago, # ^ |

This hand looks as mine after yesterday crash from bike. I fell down while I was driving up the hill :D

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+54

So it is official — in case I'll struggle with solving first problem next time, I can ask you about solution right during a contest? :)

→ Reply

9 years ago, # ^ |

-28

yes, and we will allow gray coders to help you solve.

→ Reply

MazzForces

9 years ago, # ^ |

+13

This is like giving somebody a lollypop just because they cry foul about failing in the exam. That lollypop has to be earned only in the case of passing the exam and let everybody else know there is no other way around it.

→ Reply

rhezo

9 years ago, # ^ |

Inspiring :')

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+68

I wish I knew this before Hourrank 9.

It took me 45 minutes to solve the first task as I couldn't proof the simple greedy solution. On the other hand the second task took me 5 minutes.

Next time I will be smarter and just use the discussions tab :)

→ Reply

9 years ago, # ^ |

← Rev. 3 →

More seriously.

I think that you can add a notice to the problem that this is a competitive programming contest. It is not practice problem and doesn't mean to be an easy challenge. Please do not send us any email if you don't get accepted during the contest. After the contest there will be a published editorial and you will have the opportunity to check the solution and test cases. Don't be upset, don't give up, try hard and maybe next time you will succeed — or something like that. To make sure that you don't upset beginning contestants and to show that you think of them and would like them to improve.

→ Reply

Errichto

9 years ago, # ^ |

+23

In contests with prizes I'm going to start from the second problem. After some time I will go back to the first problem. I'll go to comments and hope to maybe even find a ready solution (code). I'm allowed to do it, right?

Also, are you planning to provide solutions for second problems in the future?

→ Reply

viesis

9 years ago, # ^ |

-15

You guys are really overreacting on this. The first problem of this contest was too simple, only newbies would struggle to solve this. wanbo said that they will only help newbies by giving hints, if a problem is not that simple they would not give any hints.

→ Reply

Errichto

9 years ago, # ^ |

+21

You don't participate in any contests and know better?

Why was it too simple? Do you think that it should be harder? So why would they provide a solution in the comments?

In some contest eventually the first question will be harder than organizers expected. But yeah, we are allowed do talk about a solution in the comments.

→ Reply

sgtlaugh

9 years ago, # ^ |

← Rev. 4 →

+46

Oh no, no one is overreacting.

You see, this is the problem with HackerRank. Nobody knows what are the rules when participating. And worse, the rules keep changing from time to time (sometimes because of a glitch but whatever) and the changes are NEVER mentioned anywhere.

No I will NOT memorize what are the time limits for C/C++ or Java. No I DO NOT know that penalty for 101 Hack is the sum of all submissions but for HourRank is the last time of submission. Don't you think it is more convenient for everyone if it is mentioned EXPLICITY in the contest dashboard? Hell it is even difficult to know if a contest is rated or not. Seriously, how hard can it be to make all these information easier for contestants to access?

Regarding providing solution to the first problem, no matter what the rules are, I can respect them even if I do not like them. But the rules should be FAIR AND YOU SHOULD EXPLICITLY MENTION THEM BEFORE THE CONTEST. If you are going to provide hints/solution for the first problem in discussion, that's fine(though I think its lame). But please DO NOT discriminate whether the contestant is gray or red and DO NOT invent your own rules DURING the contest.

I know my comments may sound a bit harsh but that's just my 2 cents and please don't get me wrong. I am also a problem-setter in HackerRank, it is a great platform and I appreciate the work you guys do. But it can be a lot better with some minor modifications. My apologies if my words hurt anyone.

→ Reply