Martynas's blog

Online version of Lithuanian Olympiad in Informatics
By Martynas, 10 years ago, In English

The final round of Lithuanian Olympiad in Informatics takes place this weekend. Everybody is welcome to participate in an online version of it at http://online.lmio.lt.

Contest starts at 9:00 AM UTC on Saturday, March 21th and Sunday, March 22th. Each day participants will have 5 hours to solve 3 problems, the format is similar to IOI.

Registration will be open 30 minutes before the competition.

Problem statements will be available in Lithuanian and English.

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

On the first 2 problems, I'm getting REs. On 1 test per problem, and even if I quit after trivial starts of my programs. This is quite strange, either the memlimits are too low (unlikely) or the data are faulty or I don't know what.

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

In the last minute I figured out what was the problem with my solution of "Coffee Pot", so i submitted the 'repaired' solution, but there were only a minute or less of competition, and when the contest ended, I couldn't see the verdict, is there any way to know it? it's quite important to me, it can change mi score from 150 to 200 :O Thanks a lot! Edit: Analisis Mode is on now :D

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

Can anyone tell their solution for 3rd Problem ,Day 1 . I have only 28 point algorithm as of now.

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

    Obviously, you can perform a O(N2) shortest path algorithm to find the optimal solution. However, the weights of the edges have to be obtained beforehand, which is the hardest part of this problem.

    We tackle this subproblem by calculating the number of line segments an edge (u, v) intersects, which can be done in O(N2logN): For each vertex u you have to sort the vertices that are above u by polar angle. Now you perform a circular sweep line algorithm on the sorted vertices to check which line segments our sweep line enters or exit. The crucial crux of this problem is the condition Yi < Yi + 1 because every time we enter a line segment that belongs to vertex v we know that we have to cross this line to get to the other vertices behind v. Thus, we can use a Fenwick tree to easily obtain the number of segments we have to cross in order to get to a certain point.

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

I really enjoyed the contest, is there any official editorial for the problems? It'd be great, thanks.

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

    Sorry, but I'm afraid there isn't one in English. Here you can download an archive with solution presentations, problem statements, official solutions and test data. However, presentations are usually well illustrated with pictures, so (maybe with some help from Google Translate) you might be able to get the idea.

    → Reply