Martynas's blog

By Martynas, history, 5 years ago, In English

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.

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

»
5 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

monday at 8 AM :(
anyway this is more interesting than the physics class !!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure about ranking is working :( As I see, you wrote "Live results" so I expected the see results in contest.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve C?

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

    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   Vote: I like it +2 Vote: I do not like it

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

      Additional parameter confused me.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 abM[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   Vote: I like it 0 Vote: I do not like it

    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.

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

      There's going to be an analysis mode later today where you'll be able to test your solution.

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

        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   Vote: I like it +6 Vote: I do not like it

    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][1] + 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][0] + c[i] * d)
    

    The complexity of this solution is O(LT). There are also ways to solve it in O(NT) and O(NL).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve B?

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

Btw, I also want to know author solution for problem A.

Because my soltuions was:

  1. if M <= 15 * N then solve it with dfs in O(N * (N + M))
  2. 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.
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

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

      I don't inderstand why your solution can pass the time limit

      it'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   Vote: I like it +3 Vote: I do not like it

        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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 case

    As for your solution is "magic" meaning a randomized algorithm ?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I just missed the contest :(

Can someone post problem statement PDFs?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will test data and solutions be posted?

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Registration is still not open. Can you open it?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://online.cms.lmio.lt is unavailable for me right now :/

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I've lost my password. Is there any way to recover it?

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

    Did you lose your original Codeforces account's password too?

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

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?

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

    Please wait a few more minutes for the contest to finish before discussing the problems.

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

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.

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

    I tried two different modulos. Only 1 wrong test. Changed the base, only 3 wrong tests. So I gave up.

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

    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.

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

    I used one modulo and get AC :)

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    lol this has happened to me like 100 times xD

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

    At first I've thought there is no bug at all. :D

»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it
How to get 100 in problem B day 2
  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +29 Vote: I do not like it

    How to get 100 the hard way in problem B day 2 XD

    LOL WTF
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Great contest!

Can we see the official results of the onsite competitors?

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

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   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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?

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

        I tried everything from base = 29 to base = 14783621. And I got different wrong answer test cases every time. (only in the last subtask)

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

      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)

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

        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.

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

          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.

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

What is the official solution for problem B day 2?

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

    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   Vote: I like it 0 Vote: I do not like it

      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;
      }
      
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

        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

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

Can someone post brief solutions to each problem Please. Especially Day1 B , Day2 C and Day2 A.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi

Can 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 !

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

    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.