Разбор раунда Codeforces Round #390 (Div. 2)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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();
    }
}

Algorithm: 0 Keep tree vars: max for intersection length, l, r for final left and right bounds, go 1 1 Sort segments by their left borders, go to 2 2 Keep Min Heap of size k to store right bounds. go to 3 3 Traversing the segments, if the heap's size is less than k just add the segment's right bound to it, then go to 3. Else go to 4 4 Compare current segment's right bound with heap's peek, then go to 5 5 If it is greater than peek, then just remove peek of the heap and add the current segment's right bound to the heap, then go to 6. Else go to 7. 6 Calculate count of goods by taking difference of heap.peek()-cur.left+1. Update max, l, r and go to 7. 7 Repeat 3 - 6 until we pass all the segments, then go to 8. 8 If heap size is equals to k, then go 9, else go 10 9 Calculate count of goods by taking difference of heap.peek()-cur.left+1.Update max, l, r and go to 10 10 List k segments that contains segments [l,r]

Комментарии (50)

Показать архивные | Написать комментарий?

netman

8 лет назад, # |

Auto comment: topic has been translated by netman (original revision, translated revision, compare)

→ Ответить

haposiwe

+123

The fastest editorial in 2017

Velter

+30

Another solution of problem D. We use sweep line with events {segment_start, segment_end}. When segment starts we increase arr[pos_l]++, and when segment ends we decrease arr[pos_l]--. To find the answer, we need to check the k-th left-started segment in our array, each time for every event. If we are in pos and have segments_cnt >= k, we know that each of them has end-point >= pos, so our goal is to find k longest segments and answer is pos — po_l[k-th segment]+1. To implement arr[] we can use sparse segment tree. Code
Complexity is O(NlogN + Nlog10⁹)

PS. Is it right complexity in editorial? Should it be O(NlogN + NlogR)?

8 лет назад, # ^ |

Solution in editorial has such complexity, because I sort events in every iteration of binary search. I know how to improve complexity, but it's not so important :)

saliii

← Rev. 3 →

+40

better solution for D, which is too simpler and also much more straight to code. We know the period we want is min(ri)-max(li) between all of k periods we chose. So I sort all of the periods as {li,ri} and just for li I want k-1 periods before it which the min(ri) of them should be maximal possible. I have a set in which I keep k-1 maximum ri of previous periods. And the ans is for any i(1<i<=n) ans = max(ans, min(l[i].secon ,st.begin()->first ) — l[i].firs + 1); Complexity is O(NlogN) 23597706 thank you netman.

nima10khodaveisi

Nice :)) the best solution !

ankyizhere

Can u elaborate on how are you going to save indexes of coupons after every iteration.

As I coded, I apply the algorithm twice. At the first one, I save the maximum intersection and then at the second one, when the answer is equal to the maximum I output the i(we are at it, now) and the elements in the set.

Wow,That was simple. I was trying to update the ans in one pass and that was giving TLE. Thanks for the answer. Good solution

sieunhanbom04

It is amazing. Thank you

Ishan.nitj

Can you elaborate your approach using seg. tree? I am unabble to get it.

+14

Could you explain more about binary_search in D ?

MZuev

← Rev. 2 →

Я решил E за O(nmr + nrc).

Для каждой клетки предподсчитаем, какие строки шаблона можно приложить начиная с этой клетки: Зафиксируем строку таблицы и строку шаблона. Возьмем конкатенацию строки шаблона и строку таблицы (последнюю возможно придется повторить насколько раз, но длина будет все равно O(m + c)). Посчитаем на ней z-функцию, только при сравнении элементов на равенство будем использовать s[i + z[i]] == s[z[i]] || s[z[i]] == '?'. С помощью этих значений мы можем выполнить нужный предподсчет. Для всех пар это отработает за O(nr(m + c)

Теперь можно перебрать все клетки и пробовать к каждой из них прикладывать начало шаблона за O(nmr)

c++

hloya_ygrt

Словил вчера wa4 с той же идеей, но префикс функцией... 23605543

Строку из таблицы иногда нужно добавить больше 2-х раз. Чтобы была достаточная длина. Например, у таблицы длина 2, у шаблона 100.

Um_nik

+18

z-функция работает, потому что равенство транзитивно. У вас равенство нетранзитивно.

Например, на строчке a?b вы насчитаете 0 2 1, что не является правдой.

+13

у меня там просто 0 0 0. '?' прикладывается только к '?'. Я на контесте не вдавался в док-во корректности, так что все может быть. Это просто не первое место, где такая вещь с шаблонами проходила, а подумать над этим все время забывал.

BigBag

+32

Да, это корректный алгоритм, я точно также сдал. Но только вот есть одна проблема.

Из-за того, что z-функция может считаться неправильно для позиций, в которых записаны знаки вопроса, можно придумать тест, на котором она будет считаться за O(n²). Например, для такой строки :

a?????...?aaaaaa...a (399 вопросов, потом 800 букв a)

z-функция будет такой : 0, 0, 0, ..., 0, 800, 799, 798, ..., 1.

Т.е. во всех позициях, где записана буква a, цикл будет полностью проходить до конца строки, следовательно суммарное время работы будет как-раз O(n²).

+23

Ну тогда на строчке a???...???aaa...aaa это квадрат?

-12

В теории да, это квадрат. И в теории это TL. Но это работает, т.к. нужно было делать специальные тесты против решения. Т.е. в данном контесте это рабочее решение.

+65

То, что оно получает OK, я и так вижу. Это не делает решение правильным. Такой тест сделать можно.

Уметь сдавать медленные решения — это замечательный скилл. Но это же послеконтестовая дискуссия, сейчас мы заинтересованы не в получении OK, а в красивых решениях. Вы предложили интересный метод, но он оказался плохим. Странно оправдываться словами "ну тесты же плохие, значит решение норм".

Сама z-функция может считаться неверно для подстрок с вопросами (меньше, чем нужно), но когда знаков вопроса уже нет, она считается верно (а нам это и нужно). Т.е. после последнего вопроса будут корректные значения ф-ции.

Salim_Shebli

+29

thanks for realy good problems

SlavaSSU

+27

в Д можно еще по-другому. Отсортируем отрезки по левому концу. Переберем отрезок, левая граница которого и будет являться левой границей пересечения. Теперь из всех отрезков, левые концы к-ых не правее нас нам хочется выбрать К — 1 с наибольшими правыми концами. Корректность левых границ автоматически поддержано сортировкой(т.е. все хорошие отрезки уже рассмотрены), а чтобы выбрать максимальные К — 1 можно поддерживать сет из (К — 1) максимальных правых концов.

← Rev. 5 →

wrong solution!

haleyk100198

How do you handle the wildcard character in the KMP algorithm?

radoslav11

Can you explain it please, because I don't think you can do this with just a KMP.

PS: Obviously one can solve the problem in O(n² * C) where C is the cost of solving the 1D version of the problem. So it's enough if you tell your solution for the 1D problem.

so do you find the answer!? or I explain it?!

Please explain it, or provide a submission of an implementation code of it. :)

wrong solution!!!

pimenta

Much clearer, please :(

What is KMP for strings with '?' ?

Oh, I make a mistake about the statement....!!! sorry every one! thank you Um_nik

netflix

Loved the first problem, had to think a bit out of the box.

PoisonousPython

-10

I don't wanna be a hater, but at problem A, by "dividing" I understood that the array should be divided in 2 or more arrays. "1.Array sum is not zero. In this case we can divide array into one subarray A[1... n]." That's not called dividing, because you are left with one single array. If I'm wrong, please correct me. Thanks for reading this and I hope I didn't waste your time.

Yes, you are wrong. As the problem statement point the dividing all of array into one array is correct.

I had some trouble debugging my implementation of Div2E editorial's solution, so I'll give some hints.

If you build a straightforward G_z, i, j representation of T_i, j using std::bitset, shifting is reversed! This means that shift(G_z, x, y) should be implemented with b>>y instead of b<<y. This makes sense, because the "left" shift defined in the solution brings elements from positions with larger y indexes to positions with smaller y indexes. Using std::bitset, or any native integral types, this is actually a right shift!
The shift is actually a rotate. In other words, b>>y is not enough. Use (b<<(m-y))|(b>>y) instead.
Pattern might be larger than text, so don't forget to take y modulo m.

My implementation: 23653130

memeset

How would one go about solving D if the question was the union of all of the segments instead of the intersection?

I think a bit about it!!! And I don't think it can be solved better than O(nk). Anyone else have an idea?!

Can you share your method? The best I could think of its an O(kn^2) solution.

Sure! First, we sort segments and remove the segments that are inside another segments. We can simply prove they are useless. Now if li > lj then ri > rj. We arrange the segments with their li. Define dp[i][j] equal to the maximum union of j segments from 1 to ith! We consider two condition for ith segment to fill dp[i][j]: If the previous picked segment have any share range with this, then we choose the leftmost segment that have share range with this as k and simply dp[i][j] = dp[k][j-1]+(ri-li+1)-(rk-li+1). and If not we can update dp[i][j] from maximum of dp[k][j-1](k from 1 to k-1) and then dp[i][j] = mx[k-1][j-1]+(ri-li+1). Am I wrong?!

← Rev. 4 →

Ah, I missed out the dp transit optimization part, that's a neat observation.

Could persistent data structure help improve the algorithm? The dp transition is always going to be shift one step to the right and add the same variable if a segment is "profitable".

To be honest, I don't know about persistent data structure well! As I was thinking about it, actually, the updating is good enough to be much more optimizer! I will think about it tonight and I'll share the result(if I have any results)!

Now I think more about it I don't think persistent data structure is a feasible data structure, as there is no way to update the next state merely from the latest state. As we have to update from both the just overlapping position and the just not overlapping position it is very hard to maintain the data structure that supports update function at every version.

BoJack_Horseman

Another greedy solution for D code.

ZhassanB

My O(nlog(n)) solution using Sort and Heap for problem D (div2). 23736804

To sum up sorting takes O(nlog(n)) traversing with heap operations also O(nlog(n)). Total time complexity is also O(nlog(n)).

Arthurvtr

Problem E tags contains "fft". Could someone give me a hint about that approach?

http://codeforces.net/blog/entry/49613?#comment-335977

Thanks, it helped me a lot

Блог пользователя netman