Hello Codeforces! Did you miss Limak?
I’d like you to invite for CodeChef February Lunchtime that will start at 19:35 IST / 17:05 MSK of 25-th February 2017 (check your time zone here) and will last 3 hours. The contest starts 5 minutes later than usually to allow you to catch a breath after the AtCoder Mujin Contest that ends at 17:00 MSK.
I am an author of problems and editorials, while niyaznigmatul is a tester. I want to thank PraveenDhinwa (who is a contest admin) and suraj_sharma for their technical help. Translators: CherryTree (Russian), huzecong (Mandarin) and VNOI team (Vietnamese). Language verification: arjunarul.
There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).
You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score. The contest should be a bit easier than a Div1 Codeforces round. I honestly think that all problems are interesting and valuable — some for beginners and some for experiences competitors (IMO one particular problem is so new and beautiful). Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.
I wish you great fun and no frustrating bugs. Hope to see a lot of you in the leaderboard!
EDIT: The time of start corrected to "19:35 IST / 17:05 MSK".
EDIT2: Bump, the contest starts in 24 hours.
EDIT3: The contest is over. I hope you enjoyed problems. You can find editorials here.
And congratulations to Petr, uwi and savinov for getting the top 3 places!
"I honestly think that all problems are interesting and valuable — some for beginners and some for experiences competitors (IMO one particular problem is so new and beautiful)."
Most probably joining based on this sentence.
bump, 3 minutes
I have noticed that:
So, in case someone got 400, his rank should not be changed anymore as those who got 400 after him should rank lower than him.
However, when the ranklist first show my score was 400, my rank was 10. And just now when i refreshed the ranklist, I found out that my rank dropped to 14. Isn't this behavior impossible to happen?
Did I misunderstand the rules of ranking or there is something wrong with the ranklist?
UPD Some of the contestants ranked higher than me achieved 400 later than me.
Thanks for letting us know. Indeed something is broken with the leaderboard. We'll investigate that.
I think Codechef IOI style leaderboards take into account penalties. So maybe you have better solving time but more penalties.
But the rules stated that:
So there should not be any penalties to wrong submissions.
The problem is fixed. You can check your place now.
Can anybody give some edge cases/tricky test cases for Bear and Bribing Tree? I can't find the mistake in my logic.
Your submission wrong on this case:
The correct answer should be:
If you don't mind providing the testcase for my solution, I'd be glad, the same nickname.
The answer should be
7instead of8.BTW, it is harder to generate a counter case for you:)
Alright, thanks!
From your codechef blog: "IMO one particular problem is so new and beautiful"
So which one was it?
overflow-points problem — I've never seen something similar and the solution is just cute.
I believe, it's very sad that this problem can be solved with a purely random algorithm.
How?
I also want to know how! I didn't see any AC solution that is a "purely randomized algorithm", though I agree that one part of the solution can be done with randomization.
Here is my solution. I think it's purely random algorithm.
Can you show me how to run the randomized part of your solution? It doesn't seem to finish in minutes on my machine, even for k = 2, what I guess tries to find 3 points.
Actually, there's no magic, I just waited. I think 2-3 minutes for one new point.
You are right, it found the next point. Apparently I didn't try hard enough during the problem preparation.
Are you able to explain why it works? I have no idea why this program is able to find more than 3-4 points.
Of course I can't. During the contest I understood that I'm stupid enough to solve more than 2 problems and the only hope to get a better rank was to try this random algo... And I'm not very proud right now
But trying this algo turned out be a great idea. You solved a problem so there is nothing be ashamed of. The question is: why it works? I will try to figure that out.
I believe the main difficulty was to find ten non-collinear points with small (<=15) coordinates (after that just multiply each coordinate with 216)? I just did this: add the points with both coordinates ≤ 15 in a vector. At each step consider the current element in the vector and if it is not in the same line as any two chosen points choose it (otherwise ignore it). This gave me 19 points which was more than enough. Code
This is intended. Still, what Djok216 described is completely different.
Also, I don't agree with you about the main difficulty. Finding such non-collinear points is easy even without computer. I still think that the hardest part was to get the idea about coordinates divisible by 216.
Just generating random points and checking if the new point is ok to be taken.
but this particular problem is not IOI-style, is it? but it's interesting anyway
Why not?
Thought I couldn't solve this problem, I enjoyed solving the other three very much. Thanks for preparing such nice problemset.
Will there be an editorial?
Is there a way to see the tests on codechef?
All editorials can be found here.
You can't see tests. Likely stress testing your solution locally will help you to find a counter-test.