Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

netman's blog

Editorial. Codeforces Round #390 (Div. 2)

By netman, history, 8 years ago, translation, In English

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	long long sum = 0;
	for (int & x : a) {
		scanf("%d", &x);
		sum += x;
	}
	if (sum != 0) {
		puts("YES");
		puts("1");
		printf("%d %d\n", 1, n);
		exit(0);
	}
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (sum != 0) {
			puts("YES");
			puts("2");
			printf("%d %d\n", 1, i + 1);
			printf("%d %d\n", i + 2, n);
			exit(0);
		}
	}
	puts("NO");
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	char str[4][4 + 1];
	// cells are '.', 'o', 'x'
	for (int i = 0; i < 4; i++) {
		cin >> str[i];
	}

	auto check = [&]() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int dx = -1; dx <= 1; dx++) {
					for (int dy = -1; dy <= 1; dy++) {
						if (dx == 0 && dy == 0) continue;
						if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue;
						bool ok = true;
						for (int p = 0; p < 3; p++) {
							ok &= str[i + p * dx][j + p * dy] == 'x';
						}
						if (ok) return true;
					}
				}
			}
		}
		return false;
	};

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (str[i][j] == '.') {
				str[i][j] = 'x';
				if (check()) {
					puts("YES");
					exit(0);
				}
				str[i][j] = '.';
			}
		}
	}
	puts("NO");
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

void solve() {
	int n;
	cin >> n;
	vector<string> names(n);
	for (string& name : names) {
		cin >> name;
	}
	sort(all(names));

	auto getIdx = [&](const string& s) {
		int pos = lower_bound(all(names), s) - names.begin();
		if (pos == (int)names.size() || names[pos] != s) return -1;
		return pos;
	};

	auto splitIntoUserMessage = [](const string& s) {
		size_t pos = s.find(':');
		assert(pos != string::npos);
		return make_pair(s.substr(0, pos), s.substr(pos + 1));
	};

	auto splitIntoTokensOfLatinLetters = [](const string& s) {
		vector<string> result;
		string token;
		for (char c : s) {
			if (isalpha(c) || isdigit(c)) {
				token += c;
			}
			else {
				if (!token.empty()) {
					result.push_back(token);
				}
				token.clear();
			}
		}
		if (!token.empty()) {
			result.push_back(token);
		}
		return result;
	};

	int m;
	cin >> m;
	vector<int> who(m);
	vector<vector<char>> can(m, vector<char>(n, true));

	vector<string> messages(m);

	string tmp;
	getline(cin, tmp);

	for (int i = 0; i < m; i++) {
		string cur;
		getline(cin, cur);
		pair<string, string> p = splitIntoUserMessage(cur);
		const string& user = p.first;
		const string& message = p.second;
		who[i] = getIdx(user);
		if (who[i] != -1) {
			fill(all(can[i]), false);
			can[i][who[i]] = true;
		}
		messages[i] = message;
		vector<string> tokens = splitIntoTokensOfLatinLetters(message);
		for (const string& z : tokens) {
			int idx = getIdx(z);
			if (idx != -1) {
				can[i][idx] = false;
			}
		}
	}

	vector<vector<int>> par(m, vector<int>(n, -1));
	for (int i = 0; i < n; i++) {
		if (can[0][i]) par[0][i] = 0;
	}
	for (int msg = 0; msg + 1 < m; msg++) {
		for (int i = 0; i < n; i++) {
			if (par[msg][i] == -1) continue;
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				if (can[msg + 1][j]) {
					par[msg + 1][j] = i;
				}
			}
		}
	}
	int msg = m - 1, pos = -1;
	for (int i = 0; i < n; i++) {
		if (par[msg][i] != -1) {
			pos = i;
			break;
		}
	}
	if (pos == -1) {
		cout << "Impossible\n";
		return;
	}
	while (msg >= 0) {
		who[msg] = pos;
		pos = par[msg][pos];
		msg--;
	}
	for (int i = 0; i < m; i++) {
		cout << names[who[i]] << ":" << messages[i] << "\n";
	}
	return;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin >> t; // number of tests

	while (t--) {
		solve();
	}
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int nextInt() {
	int x = 0, p = 1;
	char c;
	do {
		c = getchar();
	} while (c <= 32);
	if (c == '-') {
		p = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * p;
}

#define all(x) (x).begin(), (x).end()

const int N = (int)3e5 + 5;
const int MAX_VAL = (int)1e9;

int n;
ll l[N], r[N];

struct event {
	ll x;
	int c;
	event() {}
	event(ll x, int c) : x(x), c(c) {}
};

pair<ll, int> check(ll len) {
	if (len == 0) return make_pair(0LL, n);
	static vector<event> evs;
	evs.resize(0);
	for (int i = 1; i <= n; i++) {
		if (r[i] - len > l[i]) {
			evs.push_back(event(l[i], 1));
			evs.push_back(event(r[i] - len, -1));
		}
	}
	sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; });
	reverse(all(evs));
	int cnt = 0, maxiCnt = 0;
	ll bestPos = 0;
	while (evs.size() > 0) {
		ll x = evs.back().x;
		while (evs.size() > 0 && evs.back().x == x) {
			cnt += evs.back().c;
			evs.pop_back();
		}
		if (cnt > maxiCnt) {
			maxiCnt = cnt;
			bestPos = x;
		}
	}
	return make_pair(bestPos, maxiCnt);
}

vector<int> getAns(ll len) {
	if (len == 0) {
		vector<int> res(n);
		iota(all(res), 1);
		return res;
	}
	ll pos = check(len).first;
	vector<int> res;
	for (int i = 1; i <= n; i++) {
		if (pos >= l[i] && pos < r[i] - len) {
			res.push_back(i);
		}
	}
	return res;
}

int main() {
	n = nextInt();
	int k = nextInt();
	for (int i = 1; i <= n; i++) {
		l[i] = nextInt();
		r[i] = nextInt() + 2;
	}
	ll l = 0, r = MAX_VAL + MAX_VAL + 5;
	while (r - l > 1) {
		ll mid = (l + r) >> 1;
		if (check(mid).second >= k) l = mid;
		else r = mid;
	}

	vector<int> ans = getAns(l);

	cout << l << endl;
	assert((int)ans.size() >= k);
	ans.resize(k);
	for (int i : ans) {
		printf("%d ", i);
	}
	puts("");
}

Tutorial is loading...

C++ code

#include <bits/stdc++.h>

using namespace std;

const int N = (int)404;
const int ALPHA = 26;

bitset<N> b[ALPHA][N];
char patt[N][N];
bitset<N> result[N];

bitset<N> getShifted(const bitset<N>& b, int len, int shift) {
	assert(0 <= shift && shift < len);
	return (b >> shift) | (b << (len - shift));
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n, m, r, c;
	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++) {
		static char str[N];
		scanf("%s", str);
		for (int j = 0; j < m; j++) {
			b[(int)(str[j] - 'a')][i][j] = true;
		}
	}
	
	scanf("%d%d", &r, &c);

	for (int i = 0; i < n; i++) {
		result[i] = ~result[i];
	}

	for (int i = 0; i < r; i++) {
		scanf("%s", patt[i]);
		for (int j = 0; j < c; j++) {
			if (patt[i][j] == '?') continue;
			int c = patt[i][j] - 'a';
			int shiftByX = (((-i) % n) + n) % n;
			int shiftByY = (((j) % m) + m) % m;
			for (int x = 0; x < n; x++) {
				int nx = (x + shiftByX);
				if (nx >= n) nx -= n;
				result[nx] &= getShifted(b[c][x], m, shiftByY);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			putchar(result[i][j] ? '1' : '0');
		}
		puts("");
	}
}

Java code

import java.io.*;
import java.util.*;

public class Main {

    static class InputReader {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;
        InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);
            stringTokenizer = null;
        }
        String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException ex) {
                    ex.printStackTrace();
                    throw new RuntimeException(ex);
                }
            }
            return stringTokenizer.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static int[] newBitSet(int n) {
        return new int[(n + 31) / 32];
    }

    static void setBit(int[] a, int pos) {
        a[pos >>> 5] |= (1 << (pos & 31));
    }

    static boolean getBit(int[] a, int pos) {
        return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0;
    }

    static void setAll(int[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = ~0;
        }
    }

    static void resetAll(int[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = 0;
        }
    }

    static void andXYtoX(int[] x, int[] y) {
        for (int i = 0; i < x.length; i++) {
            x[i] &= y[i];
        }
    }

    static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) {
        int[] z = shl[ch][shift & 31][x];
        int delta = (shift >>> 5);
        for (int i = delta; i < to.length; i++) {
            to[i - delta] |= z[i];
        }
    }

    static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) {
        int[] z = shr[ch][shift & 31][x];
        int delta = (shift >>> 5);
        for (int i = 0; i + delta < to.length; i++) {
            to[i + delta] |= z[i];
        }
    }

    static void printBitset(int a[], int l, int r) {
        for (int i = l; i <= r; i++) {
            System.err.print(getBit(a, i) ? '1' : '0');
        }
        System.err.println();
    }

    static final int ALPHA = 26;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();

        int[][][][] shl = new int[ALPHA][32][n][];
        int[][][][] shr = new int[ALPHA][32][n][];

        for (int c = 0; c < ALPHA; c++) {
            for (int sh = 0; sh < 32; sh++) {
                for (int i = 0; i < n; i++) {
                    shl[c][sh][i] = newBitSet(m);
                    shr[c][sh][i] = newBitSet(m);
                }
            }
        }

        String[] s = new String[n];

        for (int i = 0; i < n; i++) {
            s[i] = in.next();
            for (int j = 0; j < m; j++) {
                int c = s[i].charAt(j) - 'a';
                for (int sh = 0; sh < 32; sh++) {
                    if (j - sh >= 0) {
                        setBit(shl[c][sh][i], j - sh);
                    }
                    if (j + sh < m) {
                        setBit(shr[c][sh][i], j + sh);
                    }
                }
            }
        }

        int r = in.nextInt();
        int c = in.nextInt();

        String[] patt = new String[r];

        int[][] res = new int[n][];

        for (int i = 0; i < n; i++) {
            res[i] = newBitSet(m);
            setAll(res[i]);
        }

        int[] tmp = newBitSet(m);

        for (int i = 0; i < r; i++) {
            patt[i] = in.next();
            for (int j = 0; j < c; j++) {
                if (patt[i].charAt(j) == '?') continue;
                int cur = patt[i].charAt(j) - 'a';
                int shiftByX = (((-i) % n) + n) % n;
                int shiftByY = (((j) % m) + m) % m;

                for (int x = 0; x < n; x++) {
                    int nx = x + shiftByX;
                    if (nx >= n) nx -= n;
                    resetAll(tmp);
                    leftShiftAndOr(cur, shiftByY, x, shl, tmp);
                    rightShiftAndOr(cur, m - shiftByY, x, shr, tmp);
                    andXYtoX(res[nx], tmp);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(getBit(res[i], j) ? '1' : '0');
            }
            out.println();
        }

        out.close();
    }
}

Full text and comments »

Tutorial of Codeforces Round 390 (Div. 2)

edirorial, analysis, 390

+108

netman
8 years ago
42

Codeforces Round #390 (Div. 2)

By netman, history, 8 years ago, translation, In English

THi Codeforces!

I'm glad to announce that today at 17:35 MSK will take place first round in the new year — Codeforces Round #390 for the second division. Traditionally, first division participants will be able to take part out of competition.

Round was prepared by me, Alex netman Vistyazh.

Many thanks to Nikolay KAN Kalinin for his help in contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon platforms.

You will be offered five problems and two hours to solve them.

Scoring will be announced closer to beginning of the round.

UPD: Scoring is 500 — 1000 — 1500 — 2000 — 2500

UPD2:

There were some troubles during contest — in problem C first pretest wasn't equal to first sample, and unfortunately this problem was solved much worse than we expected. I made conclusions and next time I will estimate difficulties of problems more responsibly.

Congratulations to the winners!

Div 2:

Div 1:

UPD3:

Editorial posted!

Full text and comments »

Announcement of Codeforces Round 390 (Div. 2)

codeforces, round, 390

+252

netman
8 years ago
176

Codeforces Round #260 — Editorial

By netman, 10 years ago, translation, In English

Warning: my English is very bad.

456A - Laptops

Solution: 7407613;

In this task you need to check the existense of such pair i and j, such that i ≠ j, a[i] < a[j], b[i] > b[j]. If such i and j exist, Alex is happy.

There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays a and b like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array b, i.e there is such pair i and j that b[i] > b[j] и i < j ( $\text{[math]}$ ). i.e it means that array b is not sorted and it's means that a ≠ b.

456B - Fedya and Maths

Solutions: 7407625, 7407631;

In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way.

But we can transform our formula to this:

$\text{[math]}$

This formula is right because 5 is prime number and it's coprime with 1, 2, 3, 4.

φ(5) = 4

To solve this task we should be able to calculate remainder of division n by 4 and calculate formula for small n.

Asymptotics — $\text{[math]}$ .

There is also another solution. It uses a fast exponentiation, but not binary exponentiation. The idea of this exponentiation is the same as that of the binary exponentiation. Let we want to fast calculate xⁿmodP. Algorithm is very simple. Let process digits of n moving from end to begin. Let Result — current result and K — x^(10ⁱ), i — number of the currently processed digit (digits are numbered from the end. Used 0-indexation). During processing of digits, we must update result: $\text{[math]}$ , c[i] — i-th digit of the number n (digits are numbered from the end).

Asymptotics — $\text{[math]}$ .

456C - Boredom / 455A - Boredom

Solutions: 7407649, 7407655;

In this task we need to maximize the sum of numbers that we took. Let precalc array cnt. cnt[x] — number of integers x in array a. Now we can easily calculate the DP:

f(i) = max(f(i - 1), f(i - 2) + cnt[i]·i), 2 ≤ i ≤ n;

f(1) = cnt[1];

f(0) = 0;

The answer is f(n).

Asymptotics — O(n).

456D - A Lot of Games / 455B - A Lot of Games

Solutions: 7407663, 7407670;

To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: win[v] — Can player win if he makes a move now (players have word equal to prefix v in the prefix tree(trie)). lose[v] — Can player lose if he makes a move now (players have word equal to prefix v in the prefix tree(trie)).

if v is leaf of trie, then win[v] = false; lose[v] = true;

Else win[v] = (win[v] or (not win[i])); lose[v] = (lose[v] or (not lose[i])), such i — children of vertex v.

Let's look at a few cases:

If win[v] = false, then second player win (first player lose all games).

If win[v] = true и lose[v] = true, then first player win (he can change the state of the game in his favor).

If win[v] = true and lose[v] = false, then if $\text{[math]}$ , then first player win, else second player win.

Asymptotics — $\text{[math]}$ .

456E - Civilization / 455C - Civilization

Solutions: 7407681, 7407683;

You can see that the road system is a forest. For efficient storage component we need to use DSU. First, we need to build the initial system of roads. For each component of the initial road system, we must find the diameter of component. This can be done using a DFS or BFS. Let a — any vertex of component. Let b — furthest vertex from vertex a. Let c — furthest vertex from vertex b. Diameter equal to distance from b to c. This algorithm for finding the diameter is correct only for tree. For each component in the DSU, we know its diameter.

Now it is very easy to answer the query of the $1$st type: To know the component which contains the vertex x and output diameter of this component. Query of the $2$nd type also very easy to process: Let u — of component in which lie the vertex x, v — of component in which lie the vertex y. If u ≠ v, then we can merge components: The diameter of the new component is computed as follows:

$\text{[math]}$

Asymptotics — O(n·A^- 1(n)), где A^- 1(n) — inverse Ackermann function.

455D - Serega and Fun

Solutions: 7407693, 7407699, 7407703;

Let's change the query type 1 to two more simple requests:

Erase a number from r-th position. Insert this number after (l - 1)-th position.

Now let's keep our array as $\text{[math]}$ blocks. In each block will store the numbers themselves in such a manner as in the array a and will store an array cnt. cnt[x] — number of integers x in block. This requires O(n sqrtn) space.

Now we can fast process the queries of the 1st type. We can erase number from r-th position in $\text{[math]}$ operations. And we can insert this number after (l - 1)-th position in $\text{[math]}$ operations. Also we can fast recalc cnt after transformations.

Also we can fast process the queries of the

Unable to parse markup [type=CF_TEX]

O (\ sqrt n) $ numbers are in blocks, which are partly lie within the boundaries of the query.

To keep the size of the blocks close to $\text{[math]}$ , we need rebuild our structure after each $\text{[math]}$ -th query of the 1st type. We can rebuild structure in O(n) operations.

Asymptotics — $\text{[math]}$ .

455E - Function

Solutions: 7407711, 7452418;

In this problem you should quickly be able to compute the function described in the statement.

You may notice that this task is equivalent to next task:

Go through the array a, starting from the position of y, making (x - 1) step. Step might be: step to the left or to stay in place.

Function is calculated as follows: $\text{[math]}$ , k_i — how many times we visited the i th element of the array a.

For a fixed l is clear, it is most optimally that a minimum on the interval [l, y] has been visited by (x - (y - l)) times, and all the other numbers once.

You may notice that optimally to a[l] was a minimum.

From all this we can conclude that for a fixed l answer is — sum[y] - sum[l] + a[l]·(x - (y - l)), where sum — an array of prefix sums of array a.

Above formula can be written as follows:

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[l]·l + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[l]·l - sum[l])

You may notice that in brackets something like the equation of the line — K·X + B. That's very similar to the equation of the line: a[l]·(x - y) + a[l]·l - sum[l], where K = a[l], X = (x - y), B = a[l]·l - sum[l].

Now we must find minimum for all l and fixed X = (x - y).

We have n lines, i. e. for every element in array a one line (K_i, B_i).

Answer for query equal to:

$\text{[math]}$ , where (K_i, B_i) — i-th line. K_i = a[i], B_i = a[i]·i - sum[i].

For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires $\text{[math]}$ space, because each line lies in $\text{[math]}$ vertices. And we can answer query in $\text{[math]}$ operations. Because we visit $\text{[math]}$ vertices and each vertex need in $\text{[math]}$ operations. You can learn the theory about Convex Hull Trick here.

Full text and comments »

Tutorial of Codeforces Round 260 (Div. 1)

Tutorial of Codeforces Round 260 (Div. 2)

260, editorial

netman
10 years ago
153