Hello everyone!
I want to invite you to participate in August Clash at HackerEarth. Contest is scheduled on August, 15. Contest duration is 24 hours, so there should be some comfortable time for every timezone :)
There will be six tasks in a problemset. Five of them are standard algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the last task is an approximate problem — your score for this task depends on how good your solution is comparing to current best solution.
PrinceOfPersia is author of this problemset. Check his blog to get a taste of problems authored by him — he already prepared a lot of different interesting contests. Right now Hunger Games are running :)
I was working on this contest as a tester. I would like to say that I find this problemset interesting, I hope that several problems will be not too hard for beginners (don't give up and show your best with partial scoring) and some tasks are challenging enough to make this contest interesting for more experienced contestants. shef_2318 worked on this contest as translator — you will be provided with statements in Russian also. Also I want to thank to belowthebelt for technical help and doing his best on fixing all issues, processing all our feedback and improving HackerEarth platform.
As usual, here is one more reason for you to participate in this contest:
Top5 of leaderboard will also receive some nice prizes:
- $100 Amazon gift card + HackerEarth T-shirt
- $80 Amazon gift card + HackerEarth T-shirt
- $50 Amazon gift card + HackerEarth T-shirt
- HackerEarth T-shirt
- HackerEarth T-shirt
Good luck to everybody — I hope to see you at the scoreboard :)
Upd. Almost 10 hours passed from the start, congratulations to anta on being first to reach full score on classic part of problemset! All of you still have more than 14 hours to reach a top spot by getting 500 on classic part of problemset and beating everybody on approximate problem :)
Upd2. Less than 30 minutes left till the end. We have a close matchup between enot110 and anta; and FatalEagle is third person with full score on classic part of problemset.
Contest has ended :)
Feel free to discuss problems and everything related to contest in general :) Any feedback is welcome.
Right now I am adding editorials; soon they'll be updated with proper markup and more details for better understanding.
All solutions by other users should be already available for you.
For the problem Rasta and Kheshtak,
Were subsquares meant to be consecutive squares of the Kheshtak? Because my interpretation of "if we can turn A to S by deleting some of its rows and some of its columns" was that the rows(or columns) we left didn't have to be consecutive.
You are right; now, when you pointed it out, I also see clearly that given definition sounds wrong and misleading.
Yes, problem is about subsquares-submatrices. Consecutive ones; like 2d-extention of term "substring". So it is a rather standard hashing exercise (right now solution by setter and tester, and also an editorial for this particular problem should be already visible in "Editorial" tab). And a problem with that different definition doesn't sound like something standard at all :) Sorry for that misleading definition.
Next time feel free to ask questions/post your doubts using Comments section of particular problem. Maybe it isn't pointed out directly, but this Comments sections works as a clar system :) When somebody is posting something there, all these who are related to contest preparation or watching over contest are informed with a notification, and we are looking into your message; fixing things if needed, answering your question (if it is something which makes more sense than "can you explain me problem statement?" or "how can I get rid of TL?" — because most questions are like this, and that's very sad; honestly, it even happens that some good question is being lost among dozens of notifications about stupid spam like "I can't understand problem" and it is noticed only a few hours later... quite a lot of people are posting comments and then deleting them, but we also receive notifications about such messages) etc.
Surprisingly there was no questions like your during whole contest — neither in comments nor in my incoming messages (for all those who are asking contest-related questions by sending me messages at HE or even at other sites like Facebook — in 99% of cases you'd better post your question as comment to a problem), and quite a lot of people managed to solve this problem, plus looking at solutions which are not getting full score — most of them are solving proper problem. That's why we didn't notice issue :( I am sorry for that, once again.
The problem strongly suggests that neither the rows nor columns had to be consecutive, so I'm not surprised at all that no one asked for clarification. Contestants should be spending time thinking about the problems, not about what the setters meant to write.
I also think that for many contestants this was a show-stopper, e.g. they haven't had looked at subsequent problems at all.
By the way, any ideas for algorithm for the "sparse" version of the problem? Probably with much smaller constraints..
It's NP-hard, you can read about it here
Indeed, thanks! The reduction from Clique problem is quite simple.
Perhaps P = NP researchers are stuck and low on budget?
first: int ans=((k-1)*gcd(n,p))+1; if(ans>n) cout<<-1<<endl;
second: if(k-1>=n/gcd(n,p)) cout<<-1<<endl;
Can someone please explain how these two code produce different answer? first:WA,second:AC
Most common reason: when both k and gcd are quite large, first one may lead to integer overflow.
Thank you :), i tried long long in first code and got 100
anta was so close to defending his title from the last month! Congratulations to the winners! :)