You can see the current results of the online contest at https://leaderboard.cms.lmio.lt/online/Ranking.html

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?

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.

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

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 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 ?

Yes, they'll be published on online.lmio.lt.

Ok it is open now.

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

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

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

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 the hard way in problem B day 2 XD

#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;
	}
}

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)

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.

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.

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 .

#include <bits/stdc++.h>
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';	
}

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.