Hi everybody.
May Clash 2016 has just started. You have 24 hours to solve 6 problems, including an approximation one (tie breaker). The submission time doesn't matter so you can join whenever you want.
You get points for each test passed so do your best even if you can't solve the problem for the given constraints. Remember that not all tests are max-tests.
This time, problems are invented by niyaznigmatul so you can expect a very high quality of the problemset. I was a tester. Also, thanks to YakutovDmitriy and lightning for ideas for problems.
Top3 gets amazon gift cards, top5 gets t-shirts, top50 gets their handles showed in the first page of the leaderboard (I know, it's awesome).
I wish you great fun and no frustrating bugs.
WINNERS
So much red.
Top3 got nice scores in an approximation problem, congrats. Not only top5 solved all non-aproximation problems so I want to also mention Fcdkbear, rajat1603 and eatmore.
Thank you for participating!
What is going on with approximation problem? Now it has only verdicts AC or not.
In statement there are no information about scoring.
I answered under your HE comment. Everything seems fine. Sorry for not describing scoring precisely in the statement.
Found this only after the end of the contest, but seems that condition a[i] <= 31000000 doesn't hold for tests 7,18,39.
Oh, sorry for that. Well, I wanted to say, it was 32000000, and when I changed in generator the value from 32000 to 31000, so that it fits, I probably changed the statement by mistake, too.
One more question. Is it true that on hackerearth still there are no option to know upsolving results for approximation problem?
I don't know, you have to ask someone who is responsible for the testing system.
How to solve this problem : https://www.hackerearth.com/may-clash-16/algorithm/least-common-multiple/description/
print the first number greater than N / 2 whose prime factorization has just 1 prime number.
Could you please kindly provide a proof? I've been trying to understand why this works for a while.
Think at all the numbers smaller than or equal to N / 2, they all can be multiplied by 2 and you obtain a number in the interval [N/2,N] , LCM(1,2,3..N) = LCM(N/2,N/2+1,...N). We know now that the number we seek is greater than N / 2. Let P be the first prime number greater than N / 2. P multiplied by 2 is greater than N, we need to take the prime number P in the LCM, and the only number that contains it is P itself. We narrowed the search to the interval [N/2,P]. Any number in this interval multiplied by 2 gives a number greater than N. Suppose we have a number of the form a^x where a is a prime, and a^x is in the interval [N/2,P]. a^(x-1) is smaller than N / 2 and a^(x+1) is bigger than N, this means that x is the greatest power of a in the interval [1,N]. If a^x is smaller than P than the answer is a^x, if not the answer is P. P can also be written as P^1 ( a^x where a is a prime).
What you have said is correct but unfortunately does not prove the required result. Although you have correctly established that the answer must be at most the first power of a prime greater than N/2, it appears more difficult to prove that the answer will always be equal to this. In particular, what if LCM(1...N) has p^k in its factorisation, and the largest number which contains p^k is of the form a*p^k (i.e. the answer is of form a*p^k).
So far with the help of JoeyWheeler, it is clear that for sufficiently large N the required answer will be of the form p^k.
Proof only for large N: suppose that answer is W = a*p^k with a > 1 and with W at most N/2 + O(logN) because it is at most the first prime after N/2.
Then we can find that W + p^k > N (otherwise we could simply use (a+1)*p^k to get p^k). Now, p^k = W/a <= W/2 = (N/2 + O(logN))/2 = N/4 + O(logN). Therefore we can arrive at W + p^k <= 3N/4 + O(logN) which clearly gives 3N/4 + O(logN) <= N for large N. Therefore, for larger N all numbers of form a*p^k with a>1 can be moved to (a+1)*p^k instead.
So the question unfortunately still remains: how do we prove this for small N as well? Maybe it is just a coincidence that for smaller N, this approach still holds, or maybe there is a better proof.
I discussed it today in the morning together with johnasselta and we only got the same proof you provided, working for big enough N. So, maybe it's just a coincidence that it works for small numbers.
some hints plz for the ques tree median..very difficult to directly understand the code!!
consider values >= x as +1 and < x as -1 , now a path is interesting if it has sum >= 0 . This can be easily found with centroid decomposition. Now u are allowed to change the value of a node , so u pick a node with value -1 and change it to +1 , this adds 2 to the sum of all paths passing through this node. so u just need to count the number of paths passing from a node which has sum -1 or -2 . let this be called arr[i] , u just need to print max of arr[i] for all i from 1 to N whose value is -1 initially . The number of paths passing from a node with value -1 or -2 can be easily found with centroid decomposition.
thnks...
I feel dumb but how to find number arr[i] using centroid decomposition? (I do understand how to find the number of such paths in total)
suppose the centroid is 'X' and u are at a node 'Y' and u have a map say 'MP' where MP[i] stores number of paths with sum i. so the number of paths passing through 'Y' and 'X' is mp[-1 — sum] + mp[-2 — sum] where sum = sum from 'x' to 'y' + also the summation of this value for Y's subtree . This will give us number of paths with sum -1 or -2 passing through each node. Code
Suppose the current centroid is x and the subtrees you want to explore with respect to this centroid are rooted at v1, v2.....vk.
You can update arr[i] values by passing through the k subtrees in two phases. You can visit the sub-trees in the order v1, v2....vk once and then in reverse order vk, vk - 1.....v1 once and update arr[i] values for each required node.
This can be done by maintaining a map chain where chain[cost] denotes number of chains originating at x with sum of edges equal to cost. If there are some paths from u to v passing through x with sum as - 1 or - 2 then you need to update the count of such paths for all nodes in the u - v path as well. This is precisely why we can make two passes and update the arr[i] values. In general, the increment value for a node would include the sum of increment values of all it's descendants, when the centroid x is fixed.
You can count paths crossing the centroid and ending in some vertex (you basically do this when counting all paths anyway). Paths crossing a given non-centroid vertex are those ending in its subtree when the centroid is the root, so counting them is just summing over subtrees.
Check the editorial. My code there contains comments, should be helpful.
HackerEarth May Easy '16 — 5 prizes, 6th place.
Codechef April CookOff — 10 prizes, 11th place.
HackerEarth May Clash '16 — 5 prizes, 6th place.
I'm feeling lucky.
By the way, the problems were really cool and interesting to solve. Thanks to the authors and the testers.
There is an editorial under each problem (except for the approximation one). Thank you for participating.