### Martynas's blog

By Martynas, history, 3 years ago,

Once again you are invited to participate in the online mirror of the final stage of Lithuanian Olympiad in Informatics!

The format of the competition is similar to IOI: 2 days with 3 tasks in 5 hours, just the choice of languages is more limited (programming: C/C++, statements: English/Lithuanian). Day 1 contest will start on Friday, March 23 at 15:00 UTC and day 2 on Saturday, March 24 at 9:00 UTC.

Update: Congratulations to the winners! See the results of online and onsite contests.

Online:

Onsite:

• +35

 » 3 years ago, # |   0 At the same time we have our national competition so I won't be able to participate in online mirror. Can you please leave server open for at least a few days (like analysis mode) so I can make my own "virtual competition" (problems from previous years were very interesting and I would really like to take part)?
•  » » 3 years ago, # ^ |   +8 Yes, most likely there will be analysis mode after both contests finish.
•  » » » 3 years ago, # ^ |   0 Great, thank you.
 » 3 years ago, # |   0 Auto comment: topic has been updated by Martynas (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +5 Where can I find previous years' problems?
•  » » 3 years ago, # ^ |   +3 Good question. 2015 problems are here, and I'll find the other years later.
 » 3 years ago, # |   +6 What does the 'M' in 'LMIO' stands for? And it is "Lithuanian Olympiad in Informatics", but why is the short form 'LMIO' but not 'LMOI'?
•  » » 3 years ago, # ^ |   +16 LMIO is the initialism of the Lithuanian name of the olympiad, and there M is for "mokinių", which means "pupils'" (the participants are high school students).
 » 3 years ago, # |   +23 Here are my ideas for problem A and B — Problem ALets assume all bus edges have cost 1, and train edges have cost 0. Now the problems becomes — Count number of nodes from which you can reach all nodes in cost  ≤ 1.Lets shrink the graph into components and make a new graph. Nodes u and v is in same component if distance from u to v is 0. This can be done in linear time.Let C be the number of nodes(component of actual graph) in new graph. Add size of ith component to answer if its node in new graph connected to all other nodes, in other words, degree of node i in new graph is C - 1.It is easy to see why this works. Complexity O(n + m). Problem BFirst thing to notice is that our answer is always an induced star graph or a triangle. The first case can be handled naively by just looking at adjacent nodes of each node. And for the second case you can take each edge and try to make a triangle with its end points.But a thing to notice is that . So there are at most nodes with degree greater than , all other nodes should have degree less than this. So, for each edge, if you iterate on the adjacency list of the node with lower degree, in total you'll take .Since there are no self loops and multiple edges, you can prove that you always get answer if you look at O(n) edges with higher weight (think about what happens if there isn't a triangle with one side in highest O(n) edges while there is a triangle somewhere else. It leads to a contradiction).It will result into something like How to solve C?
•  » » 3 years ago, # ^ |   +17 There is a faster solution to B. For each vertex consider triangles that have smallest edge opposite to this vertex (otherwise that triangle will be considered from other vertex), If this triangle doesn't use two highest edges of this vertex, we'll get better answer by replacing third edge with biggest edge from this node, so for each node we only have to consider triangle formed by two biggest edges from this node.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you please tell me how you managed to do first part in ? I got the same idea but I got an extra log2(n) factor because I used set to find element in larger set?
•  » » » 3 years ago, # ^ |   +5 I used unordered_map v[N] for that. Though it is not true O(1), but it passed.
•  » » » » 3 years ago, # ^ |   +3 Thank you.
 » 3 years ago, # |   +1 Have the servers died?
•  » » 3 years ago, # ^ |   0 i want to ask the same.
•  » » 3 years ago, # ^ |   0 it is working now !
 » 3 years ago, # |   0 The site was (and still is) lagging during the last 10 minutes (and I also had a submission that was stuck on compilation), and is now down for me (504 gateway time-out).Does anybody know anything about it?
•  » » 3 years ago, # ^ |   0 it is working now!
 » 3 years ago, # |   +2 How to solve problem A and B from day 2 ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +9 B is easy, but A is pretty hard! C needs too many strategies...
•  » » 3 years ago, # ^ | ← Rev. 3 →   +6 Here are my solutions for A and B, I hope they can be understood even though they're not very formally written. Solution for AThere's the special case n = 1, which needs to be solved separately.Solution for n > 1:Let's denote length of a string s by |s| and its substring from a-th character to b-1-th character by s[a..b].We solve the problem by using recursion. For each substring of b[0][0..i] and b[1][0..j], where 1 ≤ i ≤ |b[0]| and 1 ≤ j ≤ |b[1]|, check if it's possible to find non-negative integers x and y such that a[0]·x + y = b[0][0..i] and a[1]·x + y = b[1][0..j]. If such integers x and y exist, then check if a[k]·x + y is a substring of b[k] for every k.If that's true for every value of k, then multiply each a[k] by x and add y to it, and erase that substring from b[k]. Keep doing this until either all b's are empty or the previously mentioned condition is false. If all strings are empty, you have found one solution, even though it's not necessarily the shortest one. Solution for BUse binary search and two pointers technique to solve the problem in .Sort the given array v, and binary search for the answer k.When checking the condition for binary search, first calculate for each i a value t[i], which is the furthest index j such that j - i < b and |v[i] - v[j]| ≤ k. For the array v = [1, 1, 1, 5, 8, 8, 8, 10] and a = 3, b = 5 the array t would be [3, 3, 3, 6, 7, 7, 7, 7].Now notice that if |i - t[i]| - 1  ≥ a, then you can select a subarray from i to [i + a - 1, t[i]] ie. you can "jump" from i to range [i + a, t[i] + 1]. Because array t is increasing, then both i + a and t[i] + 1 are increasing too. We start with a queue q that contains a range $[0, 0]$, and at each i we check if there's any range [l, r] such that l ≤ i ≤ r. If there isn't any, then there's no solution for k. Otherwise we push the range [i + a, t[i]  + 1] to the queue. 80p solution for CMy 80 points solution:Let o = [1..n].Repeat the following process several times:Random shuffle o. Then start doing depth first searches starting from each o[i] for every i in 0..n - 1. Every time you encounter a cycle, evacuate the node where you found this cycle. When there are no cycles you can successfully evacuate all other houses.Because the test cases give you the number of the test case, you can try different seeds for the random number generator and find a good seed for each case.