Hello everyone. I wanted to ask if there will be any editorial for the Challenge problem RAISINS from Feb 2020 Long Challenge like the other problems have. If yes, please tell when is it going to be released.
Are there ever editorials for challenge problems? Challenge problems focus on optimization and are designed without intended solutions in mind. I have no intended non-trivial solution, and the setter and tester hasn’t mentioned any.
2 Likes
There was one for anthill.
2 Likes
yeah, I agree with @everule1, also I think there was also a lot of discussion on one of the threads about this problem. This was the only reason why I asked this question here. I wanted to see what will be said in the editorial of the problem.
Will there be any Editorial for the problem EXPECTED CHANGE Feb 2020 Long Challenge?
Right now I have a video editorial (EXPCH Video Solution - February Long Challenge 2020 - #11 by tmwilliamlin) as a substitute while I finish writing up the official editorial.
1 Like
Please also tell about what is going to be there then for the RAISINS problem.
I’ll see what solution for RAISINS I can find.
1 Like
Ideally there should be editorials for challenge problems as they have compensation value associated with it.
I have been through this - what I did was to go through contestants solutions and see what are general concepts being used and explain them in somewhat high level. But that took me good deal of time and delayed the editorial. I think you will figure something out 
4 Likes
Atleast tell the logic behind that problem, how to come up to the solution that i m seeing
cout<<1<<" “<<1<<” "<<0;??
Did you even try reading the problem? There’s not really any logic behind 1 1 0
3 Likes
If you didn’t try reading the problem, look at Tourist's secrets revealed! Improve your long challenge rank in 10 minutes! - #3 by pulkit_mittal
That’s like "Given N points output a point whose sum of distance from each point is minimum. Your score will be (correct_ans_sum_of_dist/your_sum_of_distance)*100 ".
Now many people might simply try submitting (0,0) as an answer and they might get few points based on correct answer.
Obviously the challenge problem was a bit tough to solve as compared to this example.
rather than an editorial, I think it would be better that we share and discuss our approaches, plenty of alternative logics or details could emerge. Of course, sometimes the approach is not so simple to describe and it’s up to each of us to take the time to do it. I confese myself a little lazy
3 Likes
that’s also fine for me @above. Please share what you have done here or maybe make another thread as per your wish
Actually, I am surprised I myself failed to suggest this earlier-
A LOT of people do not make use of test generation plan section of the challenge problem. They either skip it, or just casually read it without any regards or efforts to relate how it can be used to improve score. So explaining the significance of test generation plan and how it helps in scoring good score can be a solid content (in case you are still looking for it)
2 Likes
ok, I will try a simplified explanation of what I tried. I know it’s not a clear explanation neither a great solution (6th place in div1) but for sure it will be the best you can find in this forum while noone else post his/her own.
-
take N=M=30. Why not 30x33? It was suposed I was going to do that later but, as I said, I’m a lazy guy and didn’t.
-
for each one of the 900 pieces do the following:
2.1) Calculate its convex hull to keep just the relevant points (in coordinates relative to the down-left corner of the piece)
2.2) Identify its left-most, right-most, up-most and down-most points.
2.3) for each of the corners of the cake, put the piece in that corner and just one point in the other 3 corners and calculate the area of the convex hull obteined with these points, that is, the points of the current piece and the other 3 points. This will tell us how good is the current piece in each corner of the cake. -
Identify the best piece for each corner and heuristically put it in that corner (I tried to do it using as few rotations as I can, failed to implement a cuasi-A* algo to do that). This will be the initial configuration of the following optimization procedure.
-
Calculate the convex-hull of the initial configuration. You can figure out that only points of the first and last column/row will be present in the hull.
Optimizing from the initial configuration:
5) while there is time:
5.1) For each row (or column, one of them; randomly choose if rows or columns) that is present in the hull (not incluiding first and last row/column) take the rotation of x steps that have the minimum distance between left-most point of first and right-most point of last column (the similar procedure if you are rotating a column).
5.2) Calculate the new convex hull and compare its area with the best area found so far.
5.3a) If the number of steps has not reach the limit (1024), go to 5.1 (if the number of loops (from 5.1 to 5.3) we have done for this particular solution is greater than a certain value (4 or 5), include the first and last row/column in the optimization process).
5.3b) If there’s no valid rotation that reduce the area restart from 5.1 with the initial configuration.
10 Likes
thanks for posting your approach to the question @carre. I’m able to understand it really well
1 Like