Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 27th edition will be held on 23th July 2015 at 17:00 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.
Problems have been set by Devendra Agarwal and tested by wanbo. The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
If anyone are interested in sharing their knowledge, you can comment in this post or send message to me directly. We eagerly need bunch of good problems.
Because the contest is intersected with the challenge phrase of SRM 663, we decide to postpone our contest for 0.5 hour.
Thank you HellKitsune for pointing this out. I have changed the contest time. You guys can have a good rest after SRM.
Good luck and have fun!
Should be half an hour later, right now it intersects with the challenge phase of SRM 663.
I have changed the start time, now you can enjoy both contests, and have a good rest between them. Thank you for telling me the intersection.
Yeah, intersection with Topcoder SRM 663 is quite unfortunate.
BTW, is there a way to click something on that countdown page and see my local time and date, when the event is going to happen? This would make it easier to add to calendar. Maybe I'm just blind :) ...
I have changed the countdown to the fixed time, you can click the time directly to see the time at your location.
Nice! Thanks — that makes it easier :)
Auto comment: topic has been updated by wanbo (previous revision, new revision, compare).
I have been trying to solve Special LCM of Subarray problem using Mo's algorithm. code, however I failed. Can't really understand what I've been doing wrong. Maybe, someone could explain me my mistake?
Counter-example:
Answer is LCM(2, 5) = 10.
Didn't get it though. We have L=1, R=4. Thus, S = {3, 3, 2, 5} and LCM(S) = 3 * 2 * 5 = 30. By taking it by modulo 3 we should 0. Why do you say the correct answer here is 10 though?
We don't count 3 because it have 2 occurrences in our segment. Your task is to count LCM of all numbers having only 1 occurrence.
Oh, hell. I'm counting LCM of all numbers from given range when the task is to compute LCM of all single primes from the given range. Meh...
Thanks anyway. I gave up contest, because decided there must be a problem in test cases :D Problem however was in my brain :D
Why is this implementation wrong?
thanks in advance :)
Here is correct one
To correct your mistake, just replace this line
ans[q[i].i] = answer * (1 — was_three);
with this
ans[q[i].i] = answer * (1 — (cnt[3] == 1));
What's wrong with this solution for the last problem? I hope the idea is quite clear from the code.
Does anyone know where can I find editorials for 101 Hack contests?
It must appear at the problem page next to "Discussion" tab. I think it will appear soon.
Still nothing..
now available !!!
HOw to solve UNcompress String for full points ?
Well, for every position i you can store cnt[i][j] which is number of times character j appeared in uncompressed s[1..i], along with size[i] which is the length of uncompressed s[1..i].
After seeing that the answer for a query [L..R] is a difference between answer for [1..R] query and [1..L - 1] we are left with query "how many characters C present among first N characters of S?". If there is a i such that size[i] = N then we are done, you can simply output the corresponding value in cnt[][](you can find the leftmost position in size[] which is greater of equal to N with binary search). Otherwise you know that you've hit(with your binary search) a position where we had a digit(>1) in the compressed string.
Let the position be P. We know that size[P] > N and size[P - 1] < N. We also know that uncompressed S[1..P - 1] was repeated some integer number of times. [1..N] fully contains S[1..P - 1] N / size[P - 1] (integer division) times. So we are left with a "tail" which is a prefix of S[1..P - 1] of length N % size[P - 1] and we can call the same function to count the "tail". Since we do calls only when we face digits > 1, the number of recursive calls will be at most log(1018) which is the maximum value we can be asked about.
Hope the code will make it clear.
Do you solve problem D with some strange dp? I thougt about 5D dp, but I have some problem with base during the contest.
Nice tasks, only about texts I want to say something.You write everything in text but some important things was on bad places, so I spent a lot of time for understanding statements.
Three states: length, mask, pointer. Length is number of digits placed, mask is last 4 digits, pointer can be true / false. Pointer is true if we take a new placed digit (i.e. a[length + 1]) in our sum, and false if we skip this digit and take next one (i.e. a[length + 2]).
Here is my code
Thanks !
I though about that solution, but I like to say 5D dp before mask ( it looks like something pro :D ). I don't have the third thing ( pointer) in my solution. I believe that we can do dp without it.
I did (length,mask). If I'm placing 2, I jump to states with length+2 instead of length+1, and while I can place 1 or 2 after it, that just means checking if the next two sums aren't equal to the forbidden one.