KrK's blog

KTU Programming Camp 2015
By KrK, history, 9 years ago, In English

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.

Tags ktu, gym
  • Vote: I like it
  • +95
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Nice:) Some link to the results of the competition mentioned above would also be interesting (if available).

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will there be editorials for the contests ? If not editorials then please give hints to solve the various problems.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I'll put the slides of analysis, which contain the main ideas of problems. They won't explain details, though.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      when do you will post the slides?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        After all the contests (after a couple of days).

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Have you posted the slides?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            Sorry, I am a bit late. This will be done in several hours :)

            → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    because i don't have the template for line intersection just now Kappa

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

C."Reordering ones" from Day 5 isn't clear for me. Could someone explain its solution a bit more?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

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:

7 2
0 0
0 4
2 4
1 3
2 2
1 1
2 0
1 -1
1 6

The correct answer should be 21.656854.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Anyone wants to point out where I'm wrong instead of just downvoting to oblivion?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hah, it seems your test is correct & all the Accepted solutions are wrong (checked with AC solution & 3 more AC solutions)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    |\  /\  /|
| \/  \/ |
|________|
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 8   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Realy nice problems! I haveemoutions from our problems. But where Day 4 now? :(

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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):

  • Get any edge AB from convex hull
  • Find C nearest to AB. (angle ACB is greatest).

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:

A--X1--X2--X3--X4--B
| P
|
C

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

(A) is considered a correct parenthesis sequence.

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, "(()".

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found the problem G day 1 has a weak testcase. My submission got a bit typo and yet still AC

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :(

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Day one, what is test case 14 in problem E ?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

slide download link is not working

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

slides link is dead

→ Reply