The 20-th edition of Week of Code https://www.hackerrank.com/w20 starts soon: 23 May 16:00 UTC.
Monday to Friday, every day one challenge will go live, easy to hard. The maximal score decreases by 10% at the end of every 24 hours. Your submissions will run on hidden test cases at the end of every 24 hours.
The time of each challenge will be counted since it's open. It allows you to start late.
The contest is prepared by CherryTree and tested by shef_2318
The contest is rated and top 10 get T-shirts.
GL & HF
I don't see information about t-shirt at the contest page
I am waiting Monday for my big big big comment :D
Is the testing for full score on the last problem finished? Because the top scores for it (apparently blue, yellow, violet) seem really weird tbh fam.
EDIT: Yeah yeah, downvote me.
What colors are you talking about? I guess these are hackerrank colors, but I think there is no yellow color — it is orange or red.
No, CF colours. As is evident from the fact that there is no yellow colour on HR. Not everyone competes there regularly/seriously, so HR rating system is less informative than the CF one.
I'm 5th overall there, that's way overrated.
There is no yellow color in CF either — it's orange. There used to be yellow few years ago.
Besides — there is a substantial difference between HackerRank and CF. The latter gives you opportunity to participate only in short rated contests. That rating may not be relevant in case of longer contests. Hence downvotes are fully justified.
Is it officially called orange? I called it yellow because it looks yellow to me.
We are talking about a problem which had no full score solution from a single red coder (here) even with 24 hours to spare. Not that none tried. Are you sugesting that all participating reds are bad at long contests, where silly mistakes actually don't matter as much?
(I admit that the message of my original comment isn't "cheaters!", but "tell me: how much are you willing to suspend your disbelief?". I doubt everyone and everything; I need to understand the mindset of people who don't. Not getting responses won't help me.)
Do you think it's a coincidence that vastly higher-rated people (on CF, we really can't go by HR rating yet) failed the last problem, while a NK user and 2 people from the same country, without particular results or participation in HR long contests, got full scores? It really doesn't sound like one when I put it this way :D.
Your initial comment was arrogant and was suggesting that lower rated people (on CF) couldn't solve difficult problems (on HC).
In case of short contests time and accuracy are very important factors. During longer contests your problem solving skills have much bigger impact on the result. Which means that red coders don't have such a huge advantage by being very skillful and well trained. Sort of equalizer.
The separate thing is the interesting fact that the full score on the last problem was achieved by 2 people from the same high school + guy from North Korea. However I wouldn't voice such concerns without strong evidence.
That doesn't make sense tbh. First of all, I didn't deal in absolutes ("couldn't"). And previous performance is exactly what allows us to determine how many problems we could expect someone to solve! Should I call you arrogant if you don't think I'd have tourist-tier performance in all contests I attempt from now on? No, for one simple reason: I just haven't proven myself that good. If a lower-rated coder really solves a really hard problem, then all I can say is "congratulations, but I really didn't expect you to solve it"; where's the arrogance in that? When I perform way too high, I suspect myself or expect some mistake; what would it be by that standard, arrogance towards myself? Is such a thing even possible?
In two successive sentences, you declare skill both more important and less important. I'm aware you (probably) mean some kind of base/thinking skill vs thinking about details and coding, but when you consider that for high rating, one often needs to solve problems which require a lot of thinking and sometimes little coding, and that high-rated coders should at least waste less time thus have more time for thinking, then it's not enough of an explanation for this kind of inverted order.
Instead, I will propose an alternative explanation (notice that I'm providing a counterpoint to myself): pure patience/endurance matters A LOT. Reasoning: you may notice that some high-rated people simply drop out of the contest and don't try the last few problems. I personally observe that if there's a long contest with relatively easy problems, I usually have no motivation to solve them quickly and be done with it. If we extend it to people who do try the hardest problem but are only willing to spend a few hours on it at best, the current result becomes far more reasonable. (Notice I'm not dealing in absolutes here, either.)
That's why I'm here — to ask questions which get people to think and respond :D
North Koreans have been caught competing in teams before and giving no reason afterwards to think they won't do it again. They probably didn't do it this time, because they'd be comfortably first, but given past history, it's likely that the NK guy got extra help / consulted the last problem with someone. I seriously don't trust them and see no reason to until they admit to (the proven) cheating in the past. That's as much as I'm willing to give as far as accusations go; of course, there probably can't be any evidence and punishing someone without proof is
3rd wave feminismwrong.Fml, I should go to sleep.
You are right to be suspicious because it seems suspicious :( I think i would be too.
But of course i didn't cheat, didn't ask anyone about last problem or any other problem, Erdem didn't ask me anything during contest neither (don't know about North Korean guy :p)
I tried my best in all problems and i think Erdem did as well, as you said if some high rated coders didn't put enough effort into last problem, so i think it is a pretty possible result.
Another interesting example that came to my mind is Champions League Final — both teams were from the same city :)
Dark orange
I wrote correct solution in 40 minutes and about 1 hour I spent on thinking about it. I was busy on Saturday, so I submited it only on Sunday. I think, that "higher-rated people" just skipped this problem
Damn. I thought it's yellow, not orange.
I will give a reply for all your comment here.
You think NK guy may be cheated because "North Koreans have been caught competing in teams before" and you said "I seriously don't trust them". It's simply fucking racism man. You said he's blue on CF (RyongNamSan) but look at his profile. Last visit is 3 years ago, so you can't know his CP level. Look at Hristo Venev who have 3 golds and 1 silver medals on IOI, here's CF account mustrumr. Maybe he hacked the IOI system and win gold medals like that? We should investigate him xd
Let's talk about me and Murat. Look at this contest http://www.codeforces.com/contest/666/standings they're just two guys solved E, one of them is Murat. I solved it too but can't pass pretest by silly mistake. And I have several accepted on "last problem on contest" in Hackerrank that anyone else solved it. For example https://www.hackerrank.com/contests/101hack34/challenges/beautiful-segments/leaderboard
Me and Murat is practicing together more than 3 years and in a lot of contest we do the same thing. IOI selections, CF, HR, online contests. It doesn't mean we cheating because we don't cheat. If you say something like that, at least wait till the contest ends and compare me and murat's code or find some strong evidence.
And, me being violet on CF makes me stupid? Why you think I can't solve some HR questions. If E is data structure or something like that I mostly solve it. My last CF result is 18th. Murat's max rating is red, then why you can't trust him, if you trust people by being "red"?
EDIT: Look at the results of the second qualification round of Russian Code Cup 2016. http://www.russiancodecup.ru/en/championship/result/54/ I'm the 12th and solved E. But how how how HOW HOW ??????? I'm just a violet??? There're bunch of red users who can't solve it?????? Do you want to learn my secret? We participated with all Turkish CF users together, and we will win t-shirt, cut it 124234 pieces and going to FUCKING WEAR ITTTTTTTTTT!!!!!!!!!!!
BTW, there're lots of guys that are more pro than me, but I'm just skillful in Data Structures when compared to myself. It's the best thing I can do. Being violet in CF doesn't mean I'm suck, I think :(
I believe to you, if you care about it :D
I have two questions:
I don't know why I have two first questions :D
I thought it should have been Murat and me, not ME and Murat :P
If you ask why I wrote "Me and Murat" instead of "Murat and me", I don't know any specific answer. I have very shitty English and I write as came in my mind.
And my name is Erdem Kirez, but in Turkish "Kirez" is nonsense word, so most of times I'm using "Kiraz" for avoid conversation like "What is 'Kirez' means? Is it something regional? Is it your grandgrandgrandparents fault? Or just someone wrote it wrong?"
<<"North Koreans have been caught competing in teams before" and you said "I seriously don't trust them". It's simply fucking racism man.>>
It is not racism, it is statistics. Actually statement is not "North Koreans have been caught competing in teams before". In fact statement is "I don't remember any online competition, where North Koreans participated individually". They don't think, that it is cheating, they just solving problems in their comfortable manner.
About initial topic, Xellos, calm down. The problem is easy, you missed simple solution, but somebody found it, that doesn't mean he cheated.
But one guy solved the problem, isn't it stupid to not believe him because he's North Korean?
I believe, that he could solve it. But usually they solve contests in teams. These two statements are not contradict each other.
"We participated with all Turkish CF users together, and we will win t-shirt, cut it 124234 pieces and going to FUCKING WEAR ITTTTTTTTTT!!!!!!!!!!!"
Dude, this part killed me :D :D :D :D
So what is the solution for Cat-cation rentals?
Main idea of my solution: Total number of all segments used in all different queries ≤ sum n / i = O(nlogn). So lets solve each query in O(Mlog2n), M — number of used segments in query. It could be done by two-dimentional segment tree over simple minimum segment tree.
Thanks,
Could you please describe what do you store in minimum and two-dimensional segment trees?
Systests results are not shown today, but maxscores reduced. I found it illogical.
How could O(n*n*m*1024) pass in Problem- Simple Game?
It couldn't.
can you explain how to solve the dp[m][n][max-xor] in less than this complexity. Or is there a different approach?
Unfortunately I'm not the best person to explain — I'm missing one case and probably my whole solution is far from intended one :)
Edit: I found my bug — I was missing the case with K == 3 and M == 1.
Here is my big big big comment :)
At first, tasks were interesting for me. I spent a lot interesting hours in solving and that is the most important. My final place is 60, I am very happy with it. Also you had 5500 participants, it is really good number, it means people like HR contest and you are becoming bigger.
Now let's go from task to task.
First day:
First task is easy, that is normal and expected. That is way how you can invite a lot of new participants and it should be like this on every round.
Second task is already harder than I expected. It would be enough for the second day, but ok. If someone can solve it in less than 2 minutes, I don't see why other participants can't solve it in six days :) But for my opinon you should put it for the second day.
Second day:
Task from this day is my favourite on the round. Nice idea, with pretty easy implementation. It is really hard for the second day, you had 250 good submissions for 5 days, please think whether you missed level, or I am stupid :) For my opinion second day task must be on level C div 2, and this task is on level D div 2.
Third day:
I didn't manage to solve the task ( I got half points). I read tutorial and my idea was pretty similar, but I had two cases k=2 and k>2. There is two very important problems for me:
how I can prove that for k>3 all grundy numbers are equal to G[X]= X-1. I done it on paper for smaller cases and supposed that is correct for all. But please give me some correct proof.
what is way for optimization dynamic programming approache? I didn't see it. I tried a lot of thigs and it works for n<==300, also my idea was wrriting all results in code and answer each time in O(1) complexity, but we don't have enough memory( just 50kB, on Serbian contests I think it is around 500kB).
I won't write again story about level and number of good submissions, but think about it :P
Fourth day:
I will tell only : see tasks from Litvanian OI and check complexity of my solution in worst case.
Also I believe a lot of participans had solutions like my solution, for me it is not possible to write whole correct code in 10-15 minutes.
Fifth day:
Fantastic task for the last day. You didn't have to put other tasks so hard when you had this for the end. Only remark from my side that solution in complexity O(n3) and O(nD log D) gaves the same amount of points. I think contestants which separated that cases and every time worked case with smaller complexity deserve at least 6-7 points more.
Please make better pretests next time. I can not read a billion comments like : "this is expert level ? ", "this is the easiest task on round"...
See you on next round !
Testing hasn't finished yet. You are currently 55.
Test cases for the problem Jogging Cats are really weak! https://www.hackerrank.com/rest/contests/w20/challenges/cat-jogging/hackers/allllekssssa/download_solution Worst case for this solution is N^2
Here is my personal story from this contest.
In Jogging Cats I submited a solution with array (to store vertices which could potentialy form a new cycle) of size 10^5 and I forgot that in undirected graph there are in fact 2 times more directed edges. This caused seg fault and 73,6/80 points. Because of that mistake I lost 2 positions.
When I was observing the leaderboard I thought that maybe I will get 11'th place (so theoretically the worst possible, just behind the winners) but they send me a t-shirt as they don't send prizes to North Korea (and one guy in top 10 is from North Korea). And then suddenly someone got the full score on the last problem, moving me to 12, so that I can feel the full consequences of that stupied mistake.
4th task : My solution had a worst case complexity of
N * N * M * 1024. Was that the intended solution ?5th task : Can anyone give more knowledge on big — small decomposition? I can't completely figure out the editorial.
In 5th task it is enough to process vertices in non increasing order of their degree. Count all the cycles which start in the given vertex and remove it from the graph.
See FatalEagle's solution. He did it in a much simpler
I want to write something too,
Second Problem : I think it's really nice for second problem, not goes like print smth, or not some complicated simple problem, It's just good.
Fourth Problem : The problem is good but, it really made me sad that "With proper optimizations, it passes the time limit." in the editorial. Pretests are so easy to check my solution so I checked myself. Then I add some break stuff and decided it will pass. But you're the problem setter man, you're not supposed to write "With proper optimizations, it passes the time limit.", I think. You're the one who create test cases. One can simply write O(N2) solution to N = 105 problem, create easy test cases and say, "With proper optimizations, it passes the time limit."
Fifth Problem : Here's my solution https://ideone.com/62nybh In editorial you wrote some overkilled solution with complexity O(M * N2 / 3). It's easy to do in O(N * sqrt(N)), and you don't need to consider cases separately.
Sixth Problem : I liked this problem a lot, because it's really hard to come with an idea about hard data structure problem with don't involve hard data structures :P The code is not that simple too, but there's a 24 hours time for the solve it, and finding solution is harder than writing solution. Here's mine https://ideone.com/dN3HVz And I think O(N * log3N) is really big complexity, so maybe N ≤ 50000 can be better idea or you can put some strong cases on pretests.
Overall, please add some strong cases to pretests for all problems next time, it's really sad that you don't know anything about for 24 hours then you see there was a small bug, or your complexity isn't enough or something else. Or avoid problems like "With proper optimizations, it passes the time limit.", we can't know "it passes the time limit" :(
Thank you for your suggestions!
The fact is that the only necessary optimization in the DP part in the fourth problem was not to go on from the states, where the number of ways was zero (i.e. if dp[smth1][smth2][smth3] == 0, then doesn't try to go to other states from this one). So it is more like common sense rather than "necessary optimization" -- I think the wording in the editorial didn't reflect it accurately.
The maximal test case was also obvious, so it was pretty easy for anyone to ensure that their solutions will run in time.
I know it's so obvious optimization, but in the competition I thought like "It can't fit in time limits so I have to find another solution". For example usually you can use O(N * sqrt(N) * log(N)) in 2 sec. time limit but it won't be the expected solution. In this problem it goes like, write a solution, optimize the dp, check max cases, decide your solution is fast enough. But it have to be "find a solution which is fast enough and code it". They're my ideas but maybe N ≤ 100 can be better idea.
could you explain more about fifth problem sqrt decomposition solution?
Can someone explain me the detailed solution of this problem : https://www.hackerrank.com/contests/w20/challenges/synchronous-shopping . I didn't understand the editorial. Thank you!
It is dijikstra, but the vertices now are pairs (u,b) that means that we are at vertex u and we have collected all the fishes that belongs to set b (you can think b as a bitmask). So if we let the first cat to collect all fishes of set S, then the second cat have to collect all fishes from the complement of S.
Does anyone have a proof for the solution of the fourth problem? Why for K > 3, G(X) will always be X-1.