Hello, guys!
Recently ACM teams from the Baltic countries (Estonia, Latvia and Lithuania) have competed against each other in the programming camp which was held in Lithuania and was organized for the first time.
You are invited to participate in four competitions out of five in the Gym, which will be run for the four consecutive days starting from tomorrow.
Some problems in the camp were original, others were taken from old KTU contests (which are not in the Gym currently) or various local competitions that were not well-known for the participants of the camp. The competition of the day 4 was a mashup contest and consisted of Codeforces problems. As a consequence of this, it is skipped.
Have a good day and interesting contests :)
KrK
UPD: The slides of analyses which explain the solutions very briefly (some problems are not explained) can be downloaded here.
Nice:) Some link to the results of the competition mentioned above would also be interesting (if available).
Will there be editorials for the contests ? If not editorials then please give hints to solve the various problems.
I'll put the slides of analysis, which contain the main ideas of problems. They won't explain details, though.
when do you will post the slides?
After all the contests (after a couple of days).
Have you posted the slides?
Sorry, I am a bit late. This will be done in several hours :)
Why did E from the last contest have so few solutions? It was really easy for geometry, just finding all points where the polyline crosses the polygon by brute force, sorting them in the order in which they appear on the polyline and summing up distances along the polyline between the (1st and 2nd), (3rd and 4th) etc (times 2 plus polygon circumference).
because i don't have the template for line intersection just now Kappa
C."Reordering ones" from Day 5 isn't clear for me. Could someone explain its solution a bit more?
I'm fairly certain that some test cases for problem E of Day 5 are wrong (e.g., test 14)! Accepted solutions fail the following simple test case:
The correct answer should be
21.656854.Anyone wants to point out where I'm wrong instead of just downvoting to oblivion?
Hah, it seems your test is correct & all the Accepted solutions are wrong (checked with AC solution & 3 more AC solutions)
I agree, my solution (described above) fails on this too, because it doesn't consider the possibility of an inner/outer touch. That should be the only thing that needs fixing.
btw it's worth mentioning that your case looks like
Hmm Xellos, I agree with you. As someone who has failed test 14, it seems like test 14 does have a polyline that intersects with the polygon with something like an inner-outer touch (I did check that case).
EDIT: Indeed, after removing the inner/outer touch check from my original "incorrect" code, I got AC.
Realy nice problems! I haveemoutions from our problems. But where Day 4 now? :(
It seems problem J from contest 5 test cases are not so strong. I have ACed with the following solution (also the same idea as in KrK slide):
This seems correct, but it will fail when convex hull forms a triangle ABC and there are a lot of points in segment AB. Inside the triangle, add a point P:
In this example it can be seen that A-X1-P is a solution, but if you choose X4-B from the convex hull, the circle going through X4, B, P will contains some points of convex hull.
Does anyone know how to handle this case correctly?
If a point D is contained inside the circle A,B,C and is on the same side of AB as C is (as it must be as AB is a edge of the convex hull) that means
<ADB > <ACB, contradicting C being the point maximizing ACB, right?If in your case we choose X4-B and C is within the circle through X4, B, P, then we would instead choose the triangle BCX4.
I see, I mistakenly thought that X3 will be contained in circle X4-B-P, but I can see now that angle is 0, and only C can be inside that circle. Thanks :)
I may be misunderstanding something, but I found problem A from day 1 very confusing. 100735A - Strong parentheses sequence
In the first paragraph, it states that
But it doesn't say that A must be a correct parenthesis sequence, and it sounds like anything that starts with ( and ends with ) is correct, for example, "(()".
"A sequence is called a strong parenthesis sequence only if it on form (A), where A is a correct parenthesis sequence."
^This is a sentence mentioned in the problem statement itself which makes it pretty clear and unambiguous.
I was talking about the def of a correct parenthesis sequence.
A sequence is called a correct parenthesis sequence if it's the following form:
Empty sequence is considered a correct parenthesis sequence.
(A) is considered a correct parenthesis sequence.
XY is considered a correct parenthesis sequence, if both X and Y are correct parenthesis sequences.
I found the problem G day 1 has a weak testcase. My submission got a bit typo and yet still AC
Can you host the editorial file somewhere else? Its asking me to sign up which requires credit card details. I don't have a credit card. :(
Try this: KTU.
Thanks! :D
In Day one, what is test case 14 in problem E ?
It looks like we can't see test case.
slide download link is not working
slides link is dead