### Martynas's blog

By Martynas, history, 5 years ago, Following the success of last year's online competition, Lithuanian Olympiad in Informatics is again inviting everyone to participate in its online mirror on the comming Sunday and Monday, April 10–11, starting at 8 AM UTC. This time you may even receive an award from the sponsor!

The competition format is as last year (similar to IOI: 3 problems with subtasks in 5 hours each day).

All the details at online.lmio.lt.

Edit: The competition is over. Congrats DBradac, Deemo, JustasK and tabasz for solving all the problems! See scoreboard.

You can now try submitting your solutions for the tasks of both days on online.cms.lmio.lt. Later contest materials will be published on online.lmio.lt. Comments (62)
 » 5 years ago, # | ← Rev. 3 →   monday at 8 AM :(anyway this is more interesting than the physics class !!!
 » I'm not sure about ranking is working :( As I see, you wrote "Live results" so I expected the see results in contest.
•  » » You can see the current results of the online contest at https://leaderboard.cms.lmio.lt/online/Ranking.html
 » How to solve C?
•  » » You got 50 points, so probably you wrote a dp solution.In my dp there's a line like that, for(int i = l; i <= r; i++) dp[x] = min(dp[x], dp[i] + (i - x) * cost[x]; We can write it like that, for(int i = l; i <= r; i++) dp[x] = min(dp[x], dp[i] + i * cost[x]; dp[x] -= x * cost[x]; We can make a segment tree for each cleaner, such tree[i] = dp[i] + i * cost[x - 1], and next time we can just calculate the min of range. If your solution isn't like that, just ignore.BTW, how to solve 1st?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Oh, cool!I had a little bit other dp -- f[i][j], where i = 0..l, j = 0..1 If j = 0, then I have i.0 else I have i.5Additional parameter confused me.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   For the 1st problem: Make a matrix N*N let's name it M. For each node a find a pair of nodes b, and c connect to it. If M[b][c] is not visited, set M[b][c] to a, otherwise there is a cycle of length 4 between a — b — M[b][c] — c. This works in O(N2) since at each step we've to visit new pair of nodes or stop.
•  » » 5 years ago, # ^ | ← Rev. 3 →   I saw contest too late so i couldn't code anything, but i came up with an O((N + L) * T) dp solution for problem C.Let's assume i'th plower cleans segment l and r. It doesn't make sense to pass another plower between l and r.So will we cut segment [0-L] into pieces, each of them will be length at most 2*T. Then for each piece we will choose the plower with minimum cost to clean this piece.Please correct me if my sol. wrong since i couldn't submit it.
•  » » » There's going to be an analysis mode later today where you'll be able to test your solution.
•  » » » » Apparently the analysis mode is not happening today. It'll be after the contest tomorrow, and will include tasks from both days.
•  » » 5 years ago, # ^ | ← Rev. 4 →   First, it is not optimal for one plower to cross another (unless that other is not moving), as they would cover the same section of the road twice while only once would be enough and cheaper.Cleaning the section of the road will cost 2 times the price for driving that amount, because each plower has to go back. On the other hand, it may be optimal for some plower to clean a non-integer length section (like in the second example test case). To avoid floating point numbers we can multiply L and each A_i by 2, and in this new scale we'll also have a 1:1 mapping between the price and the road length cleaned.Now, we can create a DP solution. Let's say to[x][i] is the minimal amount it costs to clean the section of the road [0, x]. The index i can be either 0 or 1 – if it is 0, we can only use the plowers that have garages in the range [0, x-1], and if it is 1, we can use the machines from [0, x].To compute the value for to[x][i]: let's assume that the last plower cleaned the section of length d, that is: [x-d, x], for each d from 1 to T. For this task it is best to use the cheapest plower in that range, which costs c[i] (for i being 0 or 1, same meaning as before – whether to include plower at position x). Then we update to[x][i] = min(to[x][i], to[x-d] + c[i] * d) Afterwards we update c[i] to take into account the plower at position x - d, and update again (with 0 instead of 1 because of the plower that we've just allowed to use for the current section): to[x][i] = min(to[x][i], to[x-d] + c[i] * d) The complexity of this solution is O(LT). There are also ways to solve it in O(NT) and O(NL).
 » On 3rd problem will O(L * T * log(T)) pass?I submited it 37 seconds before the end and couldn't see if it passed or not. When I open Rankings it doesn't even appear as it has been submited. link to solution
 » How to solve B?
 » Btw, I also want to know author solution for problem A.Because my soltuions was: if M <= 15 * N then solve it with dfs in O(N * (N + M)) Otherwise do some magic until answer has not found. If I have no time and answer still has not found I will stop the program.
•  » » Lets have both adj. list and adj matrix of the graph. Then we should find a pair of rows in our matrix (i, j) such that there is a pair of integers (k, z) that M[i][k], M[i][z], M[j][k] and M[j][z] are equal to 1. This can easily be done in O(N^2) time.link to solution
•  » » » I don't inderstand why your solution can pass the time limitit's complexity is the sum of the square of degree of each node, so if the graph is nearly complet it will N^3 Am I wrong ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   No, it's not.You will visit N^2 cells at most. If you have found once M[x][y] and then find it again you should just stop your solution. In worst case you find all N^2 cells once and the whatever cell you find it will be stop the solution.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   thanks :) I have inderstood the idea
•  » » I had a similar idea : if M exeeds some value(linear to N) then there will be a solution else we make a bruteforce , but I couldn't come with a method to find the chosen nodes of the first caseAs for your solution is "magic" meaning a randomized algorithm ?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Sort, random, and so on:D It's full of magic :)Code.
 » I just missed the contest :(Can someone post problem statement PDFs?
 » Will test data and solutions be posted?
•  » » Yes, they'll be published on online.lmio.lt.
 » Very Nice problem set. I was hungry for such a Problem set :D . Hints on Problem B?What I thought for it included: I thought of creating a graph with vertices as {x , y , direction } . The out degree of each node will be exactly one and a seperate component will have exactly one cycle. We have to some how figure out number of unique x,y in a component. I think coloring might help. Was it in the right direction?I didn't saw problem C but I think I will compete tomorrow with higher motivation :D
 » Registration is still not open. Can you open it?
•  » » Ok it is open now.
 » https://online.cms.lmio.lt is unavailable for me right now :/
 » I've lost my password. Is there any way to recover it?
•  » » Did you lose your original Codeforces account's password too?
 » 5 years ago, # | ← Rev. 2 →   Problem C All tests correct except few in the last subtask. Everytime I change the modulo and base they change. (hashing) :( How do you prevent this?
•  » » Please wait a few more minutes for the contest to finish before discussing the problems.
•  » » » My bad, sorry!
 » How to solve last without hashing? I got 100 with something like quadra-hash (four different modulos) but I think this isn't the intended solution.
•  » » I tried two different modulos. Only 1 wrong test. Changed the base, only 3 wrong tests. So I gave up.
•  » » Take a string i lenght m, take a string j lenght m+1. If longest common prefix + longest common sufffix >= m, we can turn i to j. I used hash but you can do it with some suffix structure.
•  » » I used one modulo and get AC :)
•  » » » What's the magic? Could you share your code?
•  » » » »
 » I couldn't find my bug on 1st, for an hour. Here it is if(x <= end <= y) ... I hate myself most of times
•  » » 5 years ago, # ^ | ← Rev. 2 →   lol this has happened to me like 100 times xD
•  » » At first I've thought there is no bug at all. :D
 » How to get 100 in problem B day 2#include "kortos.h" // Implement this function: // - Return 1 (true) if Adomas shows his card. // - Return 0 (false) if Adomas keeps his card. int atversti(int a, int b) { if (a < 70) { if (b*a>2300 && b>a) return 0; return 1; } else { if (b*a*1.0 < a*a* double(a)*0.01*0.5 || b>a) return 0; return 1; } } 
•  » » 5 years ago, # ^ | ← Rev. 4 →   How to get 100 the hard way in problem B day 2 XD LOL WTF#include "kortos.h" int atversti(int a, int b) { int prod = a * b; if(a > 90){ // Win Big or Go Home if(a > b && prod >= 4600) return 1; return 0; } else if(a > 80){ // Win Big or Go Home if(a > b && prod >= 3000) return 1; return 0; } else if(a > 70){ // Win Big or Go Home if(a > b && prod >= 1500) return 1; return 0; } else if(a > 60){ // Settle if(a > b && prod >= 500) return 1; return 0; } else if(a > 50){ // Settle if(a > b && prod >= 200) return 1; return 0; } else{ // Win or Don't lose much if(a > b) return 1; else if(prod <= 2000) return 1; else return 0; } } 
 » Great contest!Can we see the official results of the onsite competitors?
•  » » Not official yet (pending appeals, etc.), but the onsite results are here:https://leaderboard.cms.lmio.lt/vyr/Ranking.html (same problems as the online contest)https://leaderboard.cms.lmio.lt/jau/Ranking.html (younger group, mostly different problems)
•  » » » Okay, thank you! :D
 » 5 years ago, # | ← Rev. 2 →   Hello everyone I hope you enjoyed the contest ! can someone explain the full-point solution for C ? (I saw people talking about hashing but I never used it to solve problems)
•  » » 5 years ago, # ^ | ← Rev. 5 →   Let's build graph.Let's define s[i] — the ith string from the input. len[i] — its length.u --> v, have edge if and only if len[u] + 1 == len[v] and lcp(s[u], s[v]) + lcs(s[u], s[v]) == len[u]Your task is to find max path in such graph.In order to do that you have to build strong components. After that you are able to calculate dp f[ver] — max path from the vertex ver. You can do it as f[ver] = max(f[child_of_ver]) + 1;The answer is maximal f[i] for all i.Code here.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   I used hashing with 1e9+7 too but it didn't work. :( I am not comfortable working with hashes due to their uncertain behaviour. I used P as 26 but you have used a higher value. Some reasoning Please?
•  » » » » I tried everything from base = 29 to base = 14783621. And I got different wrong answer test cases every time. (only in the last subtask)
•  » » » How about u --> v directed edge iff we can get s[v] by deleting a single character from s[u]. Then we can calculate the longest path in the graph with simple dfs Am I missing something? Why build strong components? (I'm not sure I really know what are strong components)
•  » » » » I guess it would be easier to implement the dp approach: dpi = max(dpj + 1) for all j where the following two conditions are met: 1: lenj = leni - 1 2: lcprefix(si, sj) + lcsuffix(si, sj) = lenj Of course, this assumes that you initially sort the list of words according to length. I tried to use hashing to find all the valid j for each i, but got a TLE due to poor implementation.
•  » » » » » I did the same using Hash 1e9+7 and got WA . I hashed it using a very big prime of order 10^16 yet WA. Now I think probably I was doing something wrong in my code.
 » What is the official solution for problem B day 2?
•  » » I don't know it's the expected solution but,You can find the expected value of "wait" and "don't wait" (I don't remember exact names). I calculated expected value of first 100000 raunds, then return the optimal one.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Second problem was really awesome. Still, it would be nicer if the intended minimal score for 100 was greater than 1100. I'm saying this even though I took only 89 points, but I had many startegies in my mind and I'm more than sure that much greater pointages can be obtain, but, still, congrats for the cool problems. Can you please explain your solution and say what was the obtained P? Mine was 1067 (89 points). I've found 3 optimal constants: int atversti(int a, int b) { if (a <= 33) return 1; if (a >= 74) return (a > b && b >= 37); return a > b; } 
•  » » » » I reached 1103 and then I stopped trying. I'm wondering what is the maximum p participants were able to reach. here's my code: int atversti(int a, int b) { int x = a * b; if (a >= 70){ if (b > a) return false; if (a * b < a * (a - 50)) return false; return true; } if (a > b) return true; if (a * b > 2200) return false; return true; } 
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   I obtained 1250 on sample, I didn't remember the real case but it's smaller than 1110. When submitting will open I can say it.I added something to dp calculation, if "don't wait" is bigger than "wait"-500 I choose "don't wait". For example if we are in last round and we can obtain positive score, we must take it because we can't make another move.UPD; I got 1104.6 on contest, now I can get 1107.0 :D
 » Can someone post brief solutions to each problem Please. Especially Day1 B , Day2 C and Day2 A.
•  » » 5 years ago, # ^ | ← Rev. 3 →   Day 2:  Asteroid Belt The problem is a typical BFS problem. Implementing BFS naively would suffice for 61 points. Now observe that we are only interested in the cost incurred by making vertical movements, as the horizontal movements have zero cost. Therefore, we can easily shrink each range [L, R] in row x into one node. A range [L, R] in row x will be adjacent to all ranges [A, B] in row x - 1 and x + 1 such that [A, B] intersects with [L, R]. The weight of this edge would be 1. Observe that by shrinking the ranges into one node, the number of nodes in our graph has drastically reduced to O(K), which makes our BFS run in O(K) time. This easily suffices for 100 points.Now, to find the neighbours of a particular node, I have used sets and lower_bound, which makes implementation easier. The overall complexity of my algorithm is . C++ Code#include using namespace std; const int MAXH = 10005; struct state{ // For the Queue int row_index, st, en, dist; state(int r = 0, int s = 0, int e = 0, int d = 0){ row_index = r; st = s; en = e; dist = d; } }; set < pair < int, int > > row[MAXH]; int m, n, a, b, c, d, t; int main(){ ios :: sync_with_stdio(false); cin >> m >> n; cin >> b >> a >> d >> c; cin >> t; int start_row = 0, start_col = 0, end_col = 0; for(int i = 1; i <= t; i++){ int h, p, q; cin >> h >> p >> q; row[h].insert({q, p}); // Sorted by end points if(h == a && (p <= b && q >= b)){ start_row = h; start_col = p; end_col = q; } } queue < state > q; q.push(state(start_row, start_col, end_col, 0)); while(!q.empty()){ state ret = q.front(); q.pop(); int current_row = ret.row_index; int st = ret.st; int en = ret.en; int dist = ret.dist; if(current_row == c && (st <= d && en >= d)){ cout << dist << 'n'; return 0; } for(int dif = -1; dif <= 1; dif += 2){ int next_row = current_row + dif; if(dif == 0 || dif > n) continue; auto it = row[next_row].lower_bound({st, 0}); while(it != row[next_row].end()){ if(it -> first > en && it -> second > en) break; q.push(state(next_row, it -> second, it -> first, dist + 1)); row[next_row].erase(it); it = row[next_row].lower_bound({st, 0}); } } } cout << "-1" << 'n'; } 
 » HiCan someone provide me with a link to official solutions (the official site says the solution are going to be posted but I couldn't find them )thanks !
•  » » All contest materials were published on lmio.lt yesterday (here). If you wait for them to be published on online.lmio.lt there is a possibility that you'll find some parts translated to English, however you can already try to see if Google Translate is helpful enough for understanding what's available so far.