Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

dcordb's blog

Codeforces Round #659 Editorial

By dcordb, 4 years ago, In English

We (the setters) hope you liked the problems. Here is the editorial:

Tutorial is loading...

C++ solution

#include <iostream>

#define endl '\n'

using namespace std;

void solve()
{
    int n;
    cin >> n;

    string s(200, 'a');
    cout << s << endl;

    for (int i = 0; i < n; ++i)
    {
        int u;
        cin >> u;
        s[u] = s[u] == 'a' ? 'b' : 'a';
        cout << s << endl;
    }
}

int main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; ++i)
    {
        solve();
    }

    return 0;
}

Python solution

import sys
input = sys.stdin.readline

def main():
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
    
        mx = max(a)
        ans = [ 'a' * (mx + 1) ] * (n + 1)
    
        for i, x in enumerate(a):
            who = 'a' if ans[i][x] == 'b' else 'b'
            ans[i + 1] = ans[i][:x] + who + ans[i][x + 1:]
    
        print('\n'.join(ans))    

main()

Problem idea: dcordb

Solution idea: dcordb and Devil

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int test;
	cin >> test;
	while (test--)
	{
		int n, k, l;
		cin >> n >> k >> l;
		vector<int> d(n+2, -k);
		for (int i = 1; i <= n; ++i)
			cin >> d[i];

		set<tuple<int, int, bool>> mark;
		function<bool(int, int, bool)> go = [&](int pos, int tide, bool down)
		{
			if (pos > n) return true;
			
			if (mark.find({ pos, tide, down }) != mark.end())
				return false;

			mark.insert({ pos, tide, down });

			tide += down ? -1 : +1;
			if (tide == 0) down = false;
			if (tide == k) down = true;

			if (d[pos] + tide <= l && go(pos, tide, down))
				return true;
			if (d[pos + 1] + tide <= l && go(pos + 1, tide, down))
				return true;
			return false;
		};

		if (go(0, 0, false)) cout << "Yes\n";
		else cout << "No\n";
	}

	return 0;
}

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int test;
	cin >> test;
	while (test--)
	{
		int n, k, l;
		cin >> n >> k >> l;
		vector<int> d(n+1), safe = { 0 };
		for (int i = 1; i <= n; ++i)
		{
			cin >> d[i];
			if (d[i] + k <= l)
				safe.push_back(i);
		}

		safe.push_back(n+1);
		bool ok = true;
		for (size_t i = 1; i < safe.size() && ok; ++i)
		{
			int tide = k; bool down = true;
			for (int j = safe[i-1] + 1; j < safe[i]; ++j)
			{
				tide += down ? -1 : +1;

				if (down) tide -= max(0, d[j] + tide - l);
				if (tide < 0 || d[j] + tide > l) { ok = false; break; }

				if (tide == 0) down = false;
			}
		}

		if (ok) cout << "Yes\n";
		else cout << "No\n";
	}

	return 0;
}

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

const int Alp = 20;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int test;
	cin >> test;
	while (test--)
	{
	    int n;
		string a, b;
		cin >> n >> a >> b;

		bool bad = false;
		vector<vector<int>> adj(Alp);
		for (int i = 0; i < n; ++i)
			if (a[i] != b[i])
			{
				if (a[i] > b[i])
				{
					bad = true;
					cout << "-1\n";
					break;
				}

				adj[a[i]-'a'].push_back(b[i]-'a');
				adj[b[i]-'a'].push_back(a[i]-'a');
			}

		if (bad) continue;

		vector<bool> mark(Alp);
		function<void(int)> dfs = [&](int u)
		{
			mark[u] = true;
			for (auto v : adj[u])
				if (!mark[v])
					dfs(v);
		};

		int ans = Alp;
		for (int i = 0; i < Alp; ++i)
			if (!mark[i])
				dfs(i), --ans;
		cout << ans << "\n";
	}

	return 0;
}

Problem idea: Devil

Solution idea: mnaeraxr and Devil

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int test;
	cin >> test;
	while (test--)
	{
		int n;
		cin >> n;
		
		int x = 0;
		vector<int> a(n);
		for (auto &i : a)
		{
			cin >> i;
			x ^= i;
		}

		if (x == 0)
		{
			cout << "DRAW\n";
			continue;
		}

		for (int k = 30; k >= 0; --k)
			if (x >> k & 1)
			{
				vector<int> f(2);
				for (auto &i : a) ++f[i >> k & 1];
				if (f[1] % 4 == 3 && f[0] % 2 == 0)
					cout << "LOSE\n";
				else
					cout << "WIN\n";
				break;
			}
	}

	return 0;
}

Python solution

import sys
input = sys.stdin.readline

d = { 1: 'WIN', 0: 'LOSE', -1: 'DRAW' }

def main():
    t = int(input())

    for _ in range(t):
        n = int(input())
        a = map(int, input().split())

        f = [0] * 30

        for x in a:
            for b in range(30):
                if x >> b & 1:
                    f[b] += 1

        ans = -1
        for x in reversed(range(30)):
            if f[x] % 2 == 1:
                ans = 0 if f[x] % 4 == 3 and (n - f[x]) % 2 == 0 else 1
                break

        print(d[ans])

main()

Problem idea: Devil

Solution idea: Devil and dcordb

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

const int Alp = 20;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int test;
	cin >> test;
	while (test--)
	{
	    int len;
		string a, b;
		cin >> len >> a >> b;
		
		vector<int> adj(Alp);
		vector<vector<int>> G(Alp);
		for (int i = 0; i < len; ++i)
			if (a[i] != b[i])
			{
				adj[a[i]-'a'] |= 1 << (b[i]-'a');
				G[a[i]-'a'].push_back(b[i]-'a');
				G[b[i]-'a'].push_back(a[i]-'a');
			}

		vector<bool> mark(Alp);
		function<void(int)> dfs = [&](int u)
		{
			mark[u] = true;
			for (auto v : G[u])
				if (!mark[v])
					dfs(v);
		};

		int comp = 0;
		for (int i = 0; i < Alp; ++i)
			if (!mark[i])
				dfs(i), ++comp;

		int ans = 0;
		vector<bool> dp(1<<Alp);
		dp[0] = true;
		for (int mask = 0; mask < 1<<Alp; ++mask)
			if (dp[mask])
			{
				ans = max(ans, __builtin_popcount(mask));
				for (int u = 0; u < Alp; ++u)
					if ((~mask >> u & 1) && (adj[u] & mask) == 0)
						dp[mask | 1 << u] = true;
			}

		cout << 2*Alp - comp - ans << "\n";
	}

	return 0;
}

Problem idea: Devil

Solution idea: mnaeraxr

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> mat(n, vector<int>(m));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> mat[i][j];

    vector<int> h(n * m + 1);
    vector<int> v(n * m + 1);

    for (int i = 0; i < n; ++i)
    {
        int a = 0;
        for (int j = 0; j < m; ++j)
            a = max(a, mat[i][j]);
        h[a] = 1;
    }

    for (int i = 0; i < m; ++i)
    {
        int a = 0;
        for (int j = 0; j < n; ++j)
            a = max(a, mat[j][i]);
        v[a] = 1;
    }

    vector<vector<int>> fin(n, vector<int>(m));
    queue<pair<int, int>> q;

    int x = -1, y = -1;

    for (int u = n * m; u >= 1; --u)
    {
        x += h[u];
        y += v[u];

        if (h[u] || v[u])
        {
            fin[x][y] = u;
        }
        else
        {
            int qx, qy;
            tie(qx, qy) = q.front();
            q.pop();
            fin[qx][qy] = u;
        }

        if (h[u])
            for (int i = y - 1; i >= 0; --i)
                q.push({x, i});

        if (v[u])
            for (int i = x - 1; i >= 0; --i)
                q.push({i, y});
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cout << fin[i][j] << " \n"[j + 1 == m];

    return 0;
}

Problem idea: gilcu3

Solution idea: gilcu3 and mnaeraxr

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);

	string s; cin >> s;
	int n = s.length();
	vector<int> dist(n);
	for (int i = 0; i < n; ++i)
		if (s[i] == '0') dist[i] = (i ? dist[i-1] : 0) + 1;

	vector<int> dp(n + 2), nxt(n+2, n);
	auto get = [&](int i) { return nxt[i] < n ? dp[nxt[i]] : 0; };

	for (int i = n-1; i >= 0; --i)
	{
		dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod;
		nxt[dist[i]] = i;
	}

	int ans = n;
	if (nxt[0] < n)
		ans = ((long long)get(0) * (nxt[0] + 1)) % mod;
	cout << ans << "\n";

	return 0;
}

Problem idea: Devil

Solution idea: Devil and antontrygubO_o

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

template<typename C, typename R = C>
struct dinic
{
	typedef C flow_type;
	typedef R result_type;

	static_assert(std::is_arithmetic<flow_type>::value, "flow_type must be arithmetic");
	static_assert(std::is_arithmetic<result_type>::value, "result_type must be arithmetic");

	static const flow_type oo = std::numeric_limits<flow_type>::max();

	struct edge
	{
		//int src; // not needed, can be deleted to save memory
		int dst;
		int rev;
		flow_type cap, flowp;

		edge(int src, int dst, int rev, flow_type cap, int flowp) :
			/*src(src),*/ dst(dst), rev(rev), cap(cap), flowp(flowp) {}
	};

	dinic(int n) : adj(n), que(n), level(n), edge_pos(n), flow_id(0) {}

	int add_edge(int src, int dst, flow_type cap, flow_type rcap = 0)
	{
		adj[src].emplace_back(src, dst, (int) adj[dst].size(), cap, flow_id++);
		if (src == dst) adj[src].back().rev++;
		adj[dst].emplace_back(dst, src,  (int) adj[src].size() - 1, rcap, flow_id++);
		return (int) adj[src].size() - 1 - (src == dst);
	}

	inline bool side_of_S(int u) { return level[u] == -1; }

	result_type max_flow(int source, int sink, vector<flow_type> &flow_e)
	{
		result_type flow = 0;
		while (true)
		{
			int front = 0, back = 0;
			std::fill(level.begin(), level.end(), -1);
			for (level[que[back++] = sink] = 0; front < back && level[source] == -1; ++front)
			{
				int u = que[front];
				for (const edge &e : adj[u])
					if (level[e.dst] == -1 && flow_e[rev(e).flowp] < rev(e).cap)
						level[que[back++] = e.dst] = 1 + level[u];
			}
			if (level[source] == -1)
				break;
			std::fill(edge_pos.begin(), edge_pos.end(), 0);
			std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
			{
				if (from == sink)
					return res;
				for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
				{
					edge &e = adj[from][ept];
					if (flow_e[e.flowp] == e.cap || level[e.dst] + 1 != level[from]) continue;
					flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
					if (push > 0)
					{
						flow_e[e.flowp] += push;
						flow_e[rev(e).flowp] -= push;
						if (flow_e[e.flowp] == e.cap)
							++ept;
						return push;
					}
				}
				return static_cast<flow_type>(0);
			};
			for (flow_type f; (f = find_path(source, oo)) > 0;)
				flow += f;
		}
		return flow;
	}

	result_type max_flow2(int source, int sink, vector<flow_type> &flow_e)
	{
		result_type flow = 0;
		std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
		{
			level[from] = 1;
			if (from == sink)
				return res;
			for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
			{
				edge &e = adj[from][ept];
				if (level[e.dst] == 1 || flow_e[e.flowp] == e.cap) continue;
				flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
				if (push > 0)
				{
					flow_e[e.flowp] += push;
					flow_e[rev(e).flowp] -= push;
					if (flow_e[e.flowp] == e.cap)
						++ept;
					return push;
				}
			}
			return static_cast<flow_type>(0);
		};
		
		for (bool ok = true; ok; )
		{
			int it = 0;
			std::fill(edge_pos.begin(), edge_pos.end(), 0);
			for (flow_type f; ; ++it)
			{
				std::fill(level.begin(), level.end(), -1);
				f = find_path(source, oo);
				if (f == 0)
				{
					if (it == 0) ok = false;
					break;
				}
				flow += f;
			}
		}
		return flow;
	}

	int flow_id;
private:
	std::vector<std::vector<edge>> adj;
	std::vector<int> que;
	std::vector<int> level;
	std::vector<int> edge_pos;

	inline edge& rev(const edge &e) { return adj[e.dst][e.rev]; }
};

const int inf = 25;

struct edge
{
	int u, v, w;
};

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void relabel(int n, vector<edge> &e, int k)
{
	shuffle(e.begin() + k, e.end(), rng);

	vector<vector<pair<int, int>>> adj(n);
	for (auto &i : e)
		adj[i.u].push_back({ i.v, &i-&e[0] });

	vector<edge> ne = e;
	vector<int> id(n, -1);
	id[0] = 0;
	id[n-1] = n-1;
	int sz = 1, esz = k;

	function<void(int)> dfs = [&](int u)
	{
		for (auto &v : adj[u])
		{
			if (v.second >= k)
			{
				ne[esz++] = e[v.second];
				v.second = -1;
			}
			if (id[v.first] == -1)
			{
				id[v.first] = sz++;
				dfs(v.first);
			}
		}
	};
	dfs(0);
	
	for (auto &u : adj)
		for (auto v : u)
			if (v.second >= k)
				ne[esz++] = e[v.second];
	
	for (int i = 0; i < n; ++i)
		if (id[i] == -1)
			id[i] = sz++;
			
	e = ne;
	for (auto &i : e)
	{
		i.u = id[i.u];
		i.v = id[i.v];
	}
}

struct masks
{
	int x, cost;
	vector<int> flow_e;
	
	bool operator<(const masks &o) const
	{
		return cost < o.cost;
	}
};

typedef std::chrono::_V2::system_clock::time_point timepoint;

timepoint get_time()
{
	return std::chrono::high_resolution_clock::now();
}

int get_elapsed(timepoint t)
{
	return std::chrono::duration_cast<std::chrono::milliseconds>(get_time() - t).count();
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, m, k, q;
	cin >> n >> m >> k >> q;
	vector<edge> e(m);
	for (auto &i : e) cin >> i.u >> i.v >> i.w, --i.u, --i.v;

	vector<int> mask(1 << k, -1);
	
	relabel(n, e, k);
	dinic<int> d(n);
	for (int i = 0; i < m; ++i)
		d.add_edge(e[i].u, e[i].v, ((i < k) ? inf : e[i].w));

	vector<int> flow_e(d.flow_id);
	for (int i = 0; i < k; ++i)
		flow_e[2*i] = inf;

	mask[0] = d.max_flow(0, n-1, flow_e);
	
	priority_queue<masks> pq;
	pq.push({ 0, 0, flow_e });
	while (!pq.empty())
	{
		int x = pq.top().x;
		flow_e = pq.top().flow_e;
		pq.pop();
		
		for (int j = 0; j < k; ++j)
			if ((~x >> j & 1) && mask[x | 1 << j] == -1)
			{
				auto n_flow_e = flow_e;
				n_flow_e[2 * j] = 0;
				auto t = get_time();
				mask[x | 1 << j] = mask[x] + d.max_flow2(0, n-1, n_flow_e);
				pq.push({ x | 1 << j, get_elapsed(t), n_flow_e });
			}
	}

	vector<int> cut(1 << k), bit(1 << k);
	for (int i = 1; i < 1 << k; ++i)
		bit[i] = i & -i;

	const int U = (1 << k) - 1;
	while (q--)
	{
		for (int i = 0; i < k; ++i)
			cin >> cut[1 << i];

		int ans = mask[U];
		for (int i = 1; i < 1<<k; ++i)
		{
			cut[i] = cut[i ^ bit[i]] + cut[bit[i]];
			ans = min(ans, cut[i] + mask[U ^ i]);
		}
		cout << ans << "\n";
	}

	return 0;
}

Problem idea: mnaeraxr

Solution idea: mnaeraxr and Devil

Full text and comments »

Tutorial of Codeforces Round 659 (Div. 1)

Tutorial of Codeforces Round 659 (Div. 2)

#editorial, round 659, cuba contest

+125

dcordb
4 years ago
141

Can this DP be solved in less than O(N * K)

By dcordb, history, 6 years ago, In English

Given an array with N elements you need to choose exactly K non-consecutive elements from it such that the sum of the elements will be minimum.

Constraints:

1 ≤ N ≤ 10⁵
1 ≤ K ≤ N
- 10⁹ ≤ a_i ≤ 10⁹

I know how to solve this in O(N·K) by using DP(i, m) = minimum sum that can be obtained in prefix i taking exactly m elements.

Can it be done faster than that? Thanks beforehand.

EDIT: I had an idea that was do a binary search on the answer, let's say answer should be less or equal than x, then for a prefix i the values that m can take so that DP(i, m) ≤ x are consecutive so I transformed the DP to DP(i) = range of the valid m values. But the problem with this is how to merge DP(i - 1) with DP(i - 2) in time.

Full text and comments »

dp, optimization

dcordb
6 years ago
9

Help with this problem from NEERC 2008

By dcordb, 6 years ago, In English

Hello.

I was doing this problem (problem G) from NEERC 2008.

The problem basically says that you are given N points and in a minute all the points connect to all the others points, forming segments, now you choose the center of each segment as new points an delete the old ones. You have to say the time where one point is generated by at least 2 segments or say is 0 if it never happens.

I realized that if N ≤ 3 the answer is 0, if two different segments cuts in the middle then the answer is 1. And by looking to the solutions I saw that the answer is 2 in other case. Why does this happen, can anybody proof this?

Thank you.

Full text and comments »

ad hoc, geometry, neerc

dcordb
6 years ago
2

An interesting graph problem

By dcordb, history, 6 years ago, In English

Hi.

This problem is from a Mexican Training Camp of this year, you can find it here (spanish only). The following is the abridged statement:

Given a undirected, simple and weighted graph with N nodes and M edges you should select a set of exactly N edges (you throw away the other M - N edges) and direct each of them, such that the sum of weights will be maximum, with the restriction that each node must have out-degree equal to 1 in this new directed graph; or say that there is not solution.

Constraints:

3 ≤ N ≤ 10000
3 ≤ M ≤ 50000
The weight of edges is between - 10⁵ and 10⁵

Example:

In this case the answer is 19, you can direct edges the following way:

4 to 2 (weight = 16)
2 to 1 (weight = 1)
1 to 3 (weight = -2)
3 to 2 (weight = 4)

I thought about flow but is not clear how I would do the graph, I also thought that N - 1 edges will be from the maximum spanning tree but that is wrong as well. Anyway could you help me?

Full text and comments »

graphs, constructive algorithms

dcordb
6 years ago
2

Long queue on Codeforces

By dcordb, history, 6 years ago, In English

Admins have you noticed the long queue of submissions?

Please fix it.

Full text and comments »

bug, queue

-3

dcordb
6 years ago
0

Codeforces not working properly

By dcordb, history, 7 years ago, In English

I'm having problems lately with Codeforces interface, by example sometimes the editor doesn't load properly and I can't paste my code in it, also I can't do virtual participation because the form of the time is not working. I also can't write comments on blogs.

I cleaned the cache already and the problems persists. Is anyone else having the same problems?

Admins have you seen this?? I still can't create virtual contests.

Full text and comments »

bug

dcordb
7 years ago
2

Proof of periodic sequence in Enigmatic Device NEERC 2009

By dcordb, history, 7 years ago, In English

Hi. I already solved this problem by noticing that the sequence x¹, x², x⁴, x⁸, ..., x^2ⁿ modulo 2010 is periodic with period 10 and pre-period 2. This means that $\text{[math]}$ .

I would like to know a proof for this. Could you help me? You can find the problem statement here. It's the problem E.

Thanks beforehand.

Full text and comments »

number theory, eular phi, crt, cycle

dcordb
7 years ago
1

My solution gets TLE on 712D (Memory and Scores)

By dcordb, history, 8 years ago, In English

Hi everyone. My solution to problem 712D gets TLE, even though its complexity is $\text{[math]}$ . Where d is the difference between the score of Memory and Lexa. Note that - 2·10⁵ ≤ d ≤ 2·10⁵.

The funny thing is that in my laptop (Intel Core i5, 4gb ram) my solution runs in 1.2s. What do you think about this, is CF that slow? Anyway could you help me?

Full text and comments »

tle, 712d, help

dcordb
8 years ago
4

COJ Round Contest #8 + Editorial

By dcordb, history, 8 years ago, In English

Hello everyone.

I would like to invite you to participate in the 8th COJ (Caribbean Online Judge) Round, this will be a contest with 5 problems, and three hours of duration. The problems will have Div2-like complexity and will be in English and Spanish. The contest will have ACM-ICPC format.

You can find out more about it clicking here. You can also check out the previous rounds here.

UPD1: Time of the contest has changed because of overlapping with Euro Semifinals :). The contest will start at this time.

UPD2: The contest is about to start, get in now!!.

UPD3: The contest is over. Hope you liked the problems.

Hints:

Problem A:

The last player to play wins. Note that this last player can always get what the previous player got in the previous turn plus another positive number. Watch out with n = 1 case.

Complexity: $\text{[math]}$

Problem B:

You can start from the right: i = n, decreasing k with i - 1 while k ≥ i - 1 and append to a vector the number i. Then you can append the rest of the numbers (in increasing order) to the vector.

Complexity: $\text{[math]}$

Problem C:

Note that the graph is a tree with a cycle. The probability to disconnect the graph in one step is $\text{[math]}$ and in two steps is $\text{[math]}$ . So the expected value is $\text{[math]}$ . Here c is the length of the cycle. You can do a dfs to find c.

Complexity: $\text{[math]}$

Problem D:

A number is hyperdrome if it has at most 1 digit with odd frequence. So build a graph where each node is a bitmask representing the parity of the digits's frequence of a number. Add edges between node x (0 ≤ x < 2^b) and nodes $\text{[math]}$ .

Also add a node 2^b that represents the empty set, and add and edge to itself, and to 2¹, 2², ..., 2^b - 1.

Then you can exponentiate this graph to obtain the answer.

The answer will be $\text{[math]}$ . Where a is the adjacency matrix of the graph.

Complexity: $\text{[math]}$

Problem E:

Segment Tree. In each node save the lcp of the range, and a string that is in the range. Then to combine two nodes you can do:

lcp[x] = min (lcp[2 * x], lcp[2 * x + 1], GetLCP(str[2 * x], str[2 * x + 1]))

str[x] = str[2 * x]

Where x is a node in the segment tree and GetLCP is a function that calculates the LCP for two strings. Also you should add lazy propagation to this.

Complexity: $\text{[math]}$

Full text and comments »

coj, round, caribbean, contest

dcordb
8 years ago
11

Long submission queue in CF

By dcordb, history, 8 years ago, In English

Has anyone noted that there are 5+ pages of submissions in queue?
Please admins, fix it.

Full text and comments »

long queue, bug

dcordb
8 years ago
0

Looking for a closed formula for summation

By dcordb, history, 8 years ago, In English

sin 1 + sin 3 + sin 5 + sin 7 + sin 9 + ...
Any ideas? PD: The angle is in radians.

Full text and comments »

summation, sine

dcordb
8 years ago
6

Bug: Some fonts on CF looking bad on Firefox

By dcordb, history, 8 years ago, In English

Hi, i wanted to report that some fonts are looking bad in firefox 43.0. Look at this image:

Full text and comments »

bug, huge fonts

dcordb
8 years ago
4

TLE on Timus 1989

By dcordb, 9 years ago, In English

I'm stuck in this problem:
http://acm.timus.ru/problem.aspx?space=1&num=1989

It gives me TLE on test 15, my code uses Hashing and Fenwick Tree, so it's O(mlogn). The time limit is only 0.5s. Is there a better solution? (an O(m) solution).
Thanks in advance.

Full text and comments »

palindrome, timus, hashing

dcordb
9 years ago
8

Help with this apparently dp problem (from POI)

By dcordb, 9 years ago, In English

Could you help me with this problem from the 13th POI:
http://main.edu.pl/en/user.phtml?op=showtask&task=ork&con=OI13

It seems some kind of DP, but I'm not able to get it. So far I have an idea: to keep the state of the columns and try to filling them adding a valid rectangle, but this is too slow. Could you help me? Thanks beforehand.

Full text and comments »

dp, poi

dcordb
9 years ago
11

Could you help me with this strings problem?

By dcordb, 9 years ago, In English

This is a problem from COCI 2003, here I left you the link. The problem name is VOKI (it is the third in the pdf).

http://hsin.hr/2003/national/second_day/juniors/problems.pdf

So far I have a DP approach that works in O(n * m * max(n, m)) which is too slow, could you help me to improve this?

Full text and comments »

dp, strings, subsequence

dcordb
9 years ago
3

Could you help me with this problem?

By dcordb, 9 years ago, In English

Given a sequence of N numbers (a1, a2, ..., an) you have to find the minimum number of operations to get a consecutive group of size K such that all the elements in this group have the same height. To achieve this you can increase or decrease the height of any element by 1, any number of times, each modification costs 1 operation.

Constraints: 5 <= N <= 10^6 3 <= K <= N 0 <= ai <= 10^6

Example: N = 6 K = 4 10 4 5 2 5 7

Here the solution is a group from position 2 (1-based) to position 5 (1-based), which costs 4 operations.

So far I have a solution in O(Nlog^2(N)) using a binary search + segment tree, but this timed out. Could you help me to improve this?

Full text and comments »

data structures

dcordb
9 years ago
5